D - Sum Avoidance 解説 /

実行時間制限: 5 sec / メモリ制限: 1024 MB

配点 : 1100 点

問題文

正整数 S, K が与えられます。正整数列 A = (A_1, A_2, \ldots, A_N) は、次の 2 条件を満たすとき、良い数列であるといいます。

  • 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 が成り立つ。

項数 N が最大であるような良い数列のうち、辞書順最小のものを A = (A_1, A_2, \ldots, A_N) とします。この数列の第 K 項 A_K を出力してください。ただし K > N である場合には -1 と出力してください。

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