Fibonacci sequence is the sequence of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
It is defined as follows: F(0) = 0.
F(1) = 1.
F(n) = F(n-1) + F(n-2) n >1.
Compute the number M(n) = F(n) mod 2^m where (0 <= n <= 2 147 483 647) and (0 <= m < 20).
Input.
The number T of test cases is given in the first line.
Each test case is specified by the numbers n and m, separated by space.
Output.
The number M(n). The result for each test case should be printed in a separate line.
Sample #1.
Input.
2.
11 7.
11 6.
Output.
89.
25.