Problem Statement

You are given positive integers $S$ and $K$. A sequence of positive integers $A = (A_1, A_2, \ldots, A_N)$ is said to be a good sequence when satisfying the following two conditions.

• $1\leq A_1 < A_2 < \cdots < A_N \leq S - 1$ holds.
• $\sum_{i=1}^NA_ix_i\neq S$ holds for any sequence of non-negative integers $(x_1, x_2, \ldots, x_N)$.

Let $A = (A_1, A_2, \ldots, A_N)$ be the lexicographically smallest of the good sequences with the maximum number $N$ of terms. Print the $K$-th term $A_K$ of this sequence, or -1 if $K > N$.

We will give you $T$ test cases; solve each of them.

Constraints

• $1\leq T\leq 1000$
• $3\leq S\leq 10^{18}$
• $1\leq K \leq S - 1$

Input

Input is given from Standard Input in the following format:

T
\text{case}_1
\vdots
\text{case}_T

Each case is in the following format:

S K

Output

Print $T$ lines. The $i$-th line should contain the answer for $\text{case}_i$.