Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 3987
Numbers

Time Limit: 2 Seconds      Memory Limit: 65536 KB

DreamGrid has a nonnegative integer $n$. He would like to divide $n$ into $m$ nonnegative integers $a_1, a_2, \dots, a_m$ and minimizes their bitwise or (i.e. $n=a_1 + a_2 + \dots + a_m$ and $a_1 \text{ OR } a_2 \text{ OR } \dots \text{ OR } a_m$ should be as small as possible).

Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($0 \le n < 10^{1000}, 1 \le m < 10^{100}$).

It is guaranteed that the sum of the length of $n$ does not exceed $20000$.

Output

For each test case, output an integer denoting the minimum value of their bitwise or.

Sample Input

5
3 1
3 2
3 3
10000 5
1244 10

Sample Output

3
3
1
2000
125

Author: LIN, Xi
Source: The 2017 China Collegiate Programming Contest, Qinhuangdao Site
Submit    Status