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

.
def mul(A,B):
	a,b,c,d,e,f,g,h=A[0][0],A[0][1],A[1][0],A[1][1],B[0][0],B[0][1],B[1][0],B[1][1]
	return [[(a*e+b*g)%mod,(a*f+b*h)%mod],[(e*c+d*g)%mod,(c*f+d*h)%mod]]

def findNthPower(M ,n):
    if( n == 1 ):
    	return M;
    R = findNthPower ( M , n/2 );
    #a,b,c,d=R[0][0],R[0][1],R[1][0],R[1][1]
    R = mul(R,R)
    if( n%2 == 1 ):
    	R = mul(R,M)
    return R
   

for i in range(int(raw_input())):
	a,b=map(int,raw_input().split())
	mod=pow(2,b)
	fibm = findNthPower([[1,1],[1,0]] ,a)
	#print(fibm[0][0])
	print(fibm[0][0]%mod)