Contest Duration: - (local time) (180 minutes) Back to Home
D - Sum Avoidance /

Time Limit: 5 sec / Memory Limit: 1024 MB

### 問題文

• 1\leq A_1 < A_2 < \cdots < A_N \leq S - 1 が成り立つ。
• 任意の非負整数列 (x_1, x_2, \ldots, x_N) に対して \sum_{i=1}^NA_ix_i\neq S が成り立つ。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

### 制約

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

### 入力

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


S K


### 出力

T 行出力してください。i 行目には、\text{case}_i に対する答えを出力してください。

### 入力例 1

13
3 1
3 2
7 1
7 2
7 3
7 4
10 1
10 2
10 3
10 4
10 5
2022 507
1000000000000000000 999999999999999999


### 出力例 1

2
-1
2
4
6
-1
3
6
8
9
-1
1351
-1


S = 3, 7, 10 の場合には、A は次の数列になります。

• S=3 の場合：A = (2)
• S=7 の場合：A = (2,4,6)
• S=10 の場合：A = (3,6,8,9)

Score : 1100 points

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

### Sample Input 1

13
3 1
3 2
7 1
7 2
7 3
7 4
10 1
10 2
10 3
10 4
10 5
2022 507
1000000000000000000 999999999999999999


### Sample Output 1

2
-1
2
4
6
-1
3
6
8
9
-1
1351
-1


For the cases S = 3, 7, 10, the sequence A will be as follows.

• For S=3: A = (2).
• For S=7: A = (2,4,6).
• For S=10: A = (3,6,8,9).