Today, N candies were placed on the table. At any point, for the purpose of clarity, let X represent the number of candies left on the table. Every day, at 9 PM, if the number of candies remaining is divisible by 2, the child will take exactly X/2 candies. Otherwise, he will take (X+1)/2 candies. 

In addition, every day at 10 PM, another child will come and take X//4, where the "//" here represents integer division. Please, find the number of candies left at 11 PM after T days have passed. 

Input:

The first line contains one integer, Q, the number of test cases.  
The next Q lines contain two integers, N and T.  

Output:

Output Q lines, the answer for each test case. 

Constraints:
1 ≤ Q ≤ 10
1 ≤ N ≤ 10^16
1 ≤ T ≤ 50

SAMPLE INPUT
1
2 1

SAMPLE OUTPUT
1
q=input()
i=0
while i<q:
	n,t = map(int, raw_input().split()) #size, k
	
	
	for x in xrange(t):
		if n%2==0:
			n = n - n/2
		else:
			n = n - (n+1)/2
	
		n = n - n//4
	
	
	print n
	i+=1