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

见题面

见题面