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¹⁶
1<=T<=50