TDL

시간 제한1초메모리 제한512 MB

요약

m과 k가 주어질 때, n보다 큰 수 중 n과 서로소인 m번째 정수에서 n을 뺀 값을 n과 XOR한 결과가 k가 되는 가장 작은 n을 찾는다.

난이도: 어려움10점 중 9점
유형: 정수론, 비트 연산, 수학, 완전 탐색
정답자: 아직 제출이 없습니다

문제

양의 정수 $n$ 에 대해, $f(n, m)$ 을 $x > n$ 이고 $\gcd(x, n) = 1$ 인 $m$ 번째로 작은 정수 $x$ 로 정의하자. 예를 들어 $f(5, 1) = 6$ 이고 $f(5, 5) = 11$ 이다.

$m$ 과 $(f(n, m) - n) \oplus n$ 의 값이 주어진다. 여기서 $\oplus$ 는 비트 XOR 연산이다. $(f(n, m) - n) \oplus n = k$ 인 가장 작은 양의 정수 $n$ 을 구하는 프로그램을 작성하거나, 그러한 $n$ 이 존재하지 않음을 판별하라.

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다. ( $1 \le T \le 10$ )

각 테스트 케이스는 두 정수 $k$ 와 $m$ 을 포함하는 한 줄로 주어진다. ( $1 \le k \le 10^{18}$ , $1 \le m \le 100$ )

출력

각 테스트 케이스마다 한 줄에 하나의 정수를 출력한다. $n$ 의 최솟값을 출력하고, 해가 존재하지 않으면 대신 -1을 출력한다.

예제1

예제 1
입력
```
2
3 5
6 100
```
예상 출력
```
5
-1
```