[CCPC2017秦皇岛站-G] Numbers

内存限制：64 MB 时间限制：1000 ms

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

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$.

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

样例输入 1

样例输出 1

C1753 [CCPC2017秦皇岛站-G] Numbers

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示