Given an integer $n$, you can perform the following two operations:

• $n \leftarrow n+2$, which increases $n$ by $2$.
• If $\sqrt{n}$ is an integer, $n \leftarrow \sqrt{n}$, which replaces $n$ with its square root. You gain $1$ point after performing this operation.

You need to find the minimum number of operations required to gain $k$ points.

Input

This problem contains multiple test cases.

The first line of input contains two non-negative integers $c$ and $t$, representing the test case ID and the number of test cases, respectively. $c=0$ indicates that the test case is a sample.

Each test case is then provided as follows:

• A single line containing two positive integers $n$ and $k$.

Output

For each test case:

• Output a single line containing an integer, representing the minimum number of operations required to gain $k$ points.

Examples

Input 1

0 5
6 1
1 3
14514 23333
2011112920110906 1
3 1919810233114514

Output 1

6
3
46860
15268726
7679240932458056

Note 1

This sample contains $5$ test cases.

• For the first test case, performing the first operation $5$ times and the second operation $1$ time is sufficient. It can be proven that at least $6$ operations are required.
• For the second test case, performing the second operation $3$ times is sufficient. It can be proven that at least $3$ operations are required.

Constraints

For all test cases:

• $1 \le t \le 10^5$;
• $1 \le n,k \le 10^{18}$.

• Special Property: Guaranteed $t=3$.