E. Binary Function
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

While AHF loves short descriptions, he has noticed that the descriptions for earlier problems have been longer than he wanted. Therefore, he decided to keep this problem's description as short as possible.

Let us declare function $$$f(x)$$$ for a positive number $$$x$$$ as the number of adjacent indices $$$i$$$ $$$(0 \le i \lt \lfloor{\log _2 x }\rfloor)$$$ in $$$B$$$, defined as the binary representation of $$$x$$$, meeting the condition $$$B_i \neq B_{i+1}$$$, for example, $$$f(5) = f({101}_2) = 2$$$.

You're given positive integers $$$k$$$ and $$$n$$$, calculate how many numbers $$$x$$$ exist, such that $$$1 \le x \le n$$$ and $$$f(x) = k$$$, As AHF considers this easy for only one query, He wants you to answer $$$q$$$ independent queries.

Input

On the first line of the input, you will receive a positive integer $$$q$$$ ($$$1 \le q \le 10^5$$$), which is the number of queries. On the $$$q$$$ following lines, you will receive two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le 60$$$, $$$1 \le n \le 2^{60} - 1$$$) in corresponding order.

Output

For each query, output the answer in one line.

Example
Input
10
6 2
1 60
94 3
32 5
98 3
123 2
2012 5
3443 24
54543 12
3232123 10
Output
1
0
25
0
26
34
461
0
499
536402