the-tiled-footpath-on-marine-drive

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

.

Source: hackerearth | Difficulty: EASY


Solutions: