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.