The Thue-Morse sequence is a binary sequence - an infinite sequence of zeroes and ones. The sequence is obtained by starting from the string 0, and constantly expanding it with the Boolean complement of the obtained string so far. The Boolean complement of a binary string is obtained by replacing all zeroes with ones and all ones with zeroes. This procedure therefore starts with the string 0, and successively delivers the strings 01, 0110, 01101001, 0110100110010110, and so on.
The Thue-Morse sequence has many stunning features. For example, the binary sequence is cube-free: it does not contain 000,111,010101, or more generally bbb in which b represents a random binary string. The sequence is also self-similar: if you remove every other bit from the series, you again obtain a Thue-Morse sequence. This sequence has many applications in mathematics, and is also used in chess, graphic design, weaving patterns1 and composing music.
The first line of the input contains an
integer
For each test case, print the substring of
the Thue-Morse sequence, starting at position
Input:
5
7645 37
8956 28
4724 26
8829 17
6051 12
Output:
0011001011001101001011010011001011001
0110100101100110100101101001
01100110100110010110011010
00110010110011010
010011001011