Welcome to ZOJ
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