X and Y are sitting beside a footpath on a bench on Marine Drive having a look at the beautiful sea.
(Anyone from Mumbai here ?). X is a top coder who studies at DA-IICT. His friend Y studies at some
local college from Mumbai. X always wants to show off his coding prowess so he asks puzzles to Y
and Y (being not so intelligent) cannot answer them. Then X tells the answer and Y is impressed.
Today X asks another puzzle to Y looking at the tiles on the footpath. Y is fed up of the boasting
of X. Today he wants to solve the puzzle and tell the answer to X. Help Y to solve the puzzle.
The puzzle posed by X is as follows -
Find the number of ways in which you can tile a grid of 1xn squares with 1x1 and 1x2 tiles.
Let this number be m.
Find m mod 2^k for given k.
Do the following for 't' testcases.

Input constraints :
0 ≤ n ≤ 2147483647
0 ≤ k ≤ 20
1 ≤ t ≤ 100

Input Format :
The first line contains the integer t - denoting the number of testcases.
It is followed by t lines each containing 2 space separated integers n and k
Output Format :
Output t lines each containing the answer - m mod 2^k where m is the as defined above.

SAMPLE INPUT
1
5 2

SAMPLE OUTPUT
0

Explanation

.

见题面

见题面