Link has $m$ weights, and the mass of each weight is a positive integer. It is known that Link can use these weights to measure all integer weights from $1$ to $n$ (weights can only be placed on the same side of the balance). What is the minimum possible mass of the heaviest weight Link has? Note: It is unknown whether the weights Link has can represent a weight of $n+1$ or greater.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 2 \times 10^5$).

For each test case, the input consists of a single line containing two integers $n$ and $m$ ($1 \le n, m \le 10^9$), representing the maximum weight that can be represented and the number of weights, respectively.

Output

For each test case, output a single integer representing the minimum possible mass of the heaviest weight Link has. If it is impossible to represent all weights from $1$ to $n$ using $m$ weights, output "-1".

Examples

Input 1

2
40 6
16 4

Output 1

13
-1