The numbers (each integer from to once) are written on a board. In one operation, Jesse can choose any number from the board and replace it by (Half of rounded down). Jesse wants to minimize the sum of the integers after performing exactly operations. Help Jesse.
The first line contains , the number of testcases.
Each of the following lines contain two space separated integers, and .
For each testcase, print a single line containing a single integer, the minimum sum after performing exactly operations.
3 4 1 4 3 3 10
8 5 0
For the first case, are written. Jesse picks and replaces it by . Now the board contains with sum .
For the second case, initially the board contains .
For the third case, Jesse can make everything .