A well-known puzzle is: "what is the next element in the sequence $$$1, 11, 21, 1211, 111221, 312211$$$?". In this problem we consider the binary variant.
The first element of the binary look and say sequence is 1. Each next element is generated by looking at the previous element and counting the number of digits in each group of consecutive similar digits. For example, if an element of the sequence is 110001, then the next element will be 10111011 (10 1, 11 0, 1 1, that is: two 1s, three 0s, one 1). Notice that the counts of similar digits are written down in binary.
For example, the first few elements of the sequence are generated as follows:
Your task is to calculate the $$$m$$$-th binary digit from the right of the $$$n$$$-th element in the sequence. The first element of the sequence has index 1; the rightmost binary digit of an element has index 0. If the element has $$$m$$$ or fewer binary digits, output 0.
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. $$$t$$$ test cases follow.
Each test case consists of two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^{18}$$$, $$$0 \le m \lt 10^6$$$).
For each test case, print the answer on a separate line.
104 04 14 24 34 44 54 66 36 7118999881999119725 3
1 1 0 1 1 1 0 1 1 0
The fourth element of the sequence is 111011. The first six tests print out this number in reverse: as we are increasing $$$m$$$, we are moving from right to left. The seventh test, 4 6 returns 0 as there are only six digits in the number 111011.
