Problem Statement

一个二进制序列由下面的伪代码生成：

string A = "0"
            While (A的长度小于等于n)
            创建一个和A一样长度的字符串B
            For i=0,1,...length(A)-1
            If (i 是完全平方数)
            B[i] = 1-A[i]
            Else
            B[i] = A[i]
            令A = A + B (即将B拼接在A后面)
            End While
            Return A

请注意，在上面的伪代码中，A[i]和B[i]分别表示字符串A和B中下标为i的字符（下标编号从0开始）。对“完全平方数”的定义是，对于整数i，存在整数j，使得i= j *j，则称i为完全平方数。

下面具体说明序列生成的过程：如果n=7，则在每一轮迭代中，A的取值依次为：0, 01, 0110, 01101010，所以最终产生的二进制序列就是0,1,1,0,1,0,1,0

请返回上述序列中下标为n的数字（该序列的下标从0开始）(0=<n<=2,000,000,000)

Definition