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
t = input()
while t:
	t -=1
	a,b = raw_input().split(" ")
	a = int(a)
	b = int(b)
	for i in range (0,b):
		if a%2 == 0:
			a = a - a/2
		else:
			a = a - (a+1)/2
		a = a - a/4
	print a