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 patterns¹ and composing music.

Input

The first line of the input contains an integer $t\in \mathbb{N}$ indicating the number of test cases. This is followed by $t$ lines that each describe a test case. Each of these lines consists of two integers $s$ and $l$, separated by a space.

Output

For each test case, print the substring of the Thue-Morse sequence, starting at position $s$ and is $l$ binary digits long. We index the positions of the binary digits from zero.

Example

Input:

                
            5
7645 37
8956 28
4724 26
8829 17
6051 12

Output:

                
            0011001011001101001011010011001011001
0110100101100110100101101001
01100110100110010110011010
00110010110011010
010011001011