시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 5 5 5 100.000%

문제

For a positive integer n, let us denote function f(n, m) as the m-th smallest integer x such that x > n and gcd(x, n) = 1. For example, f(5, 1) = 6 and f(5, 5) = 11.

You are given the values of m and (f(n, m) − n) ⊕ n, where “⊕” denotes the bitwise XOR operation. Please write a program to find the smallest positive integer n such that (f(n, m) − n) ⊕ n = k, or determine it is impossible.

입력

The first line of the input contains an integer T (1 ≤ T ≤ 10), denoting the number of test cases.

Each test case is denoted by a single line containing two integers k and m (1 ≤ k ≤ 1018, 1 ≤ m ≤ 100).

출력

For each test case, print a single line containing a single integer: the smallest value of n. If there is no solution, output “-1” instead.

예제 입력 1

2
3 5
6 100

예제 출력 1

5
-1