1 <= N <= 1000
Constraints according to the question .
And testcase :
29843 1 1 1 1 1 0 0 1 0 0 0 0 1 1 0 1 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 0 1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 0 1 1 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 1 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 1 1 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 0 1 1 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 0 0 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 1 1 0 1 1 1 0 0 0 1 1 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 1 1 0 1 0 0 1 0 1 0 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 0 0 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 1 1 1 0 1 1 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1 1 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 1 1 0 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 0 1 1 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 0 0 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 0 0 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 1 0 1 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 0 0 1 1 0 1 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 1 0 1 1 1 0…
//wasted half an hour writing recursive + memoization code keeping constraints in mind.