«배타적 논리합»의 반격

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

요약

a와 n이 1e18까지 주어질 때, a xor b가 n으로 나누어떨어지는 가장 작은 음이 아닌 b를 각 테스트마다 구한다.

난이도: 어려움10점 중 8점
유형: 비트 연산, 정수론, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

음이 아닌 정수 $a$ 와 $n$ 이 주어진다. $a \oplus b$ 가 $n$ 으로 나누어떨어지는 최소의 음이 아닌 정수 $b$ 를 구해야 한다.

여기서 $\oplus$ 는 비트 단위 «배타적 논리합» 연산을 나타내며, 파스칼의 «xor» 연산이나 다른 언어의 «\char 94» 연산에 해당한다. 두 수 $x$ 와 $y$ 의 비트 단위 «배타적 논리합»을 계산하려면 각 수를 이진법으로 적고, 필요하면 왼쪽에 0을 채워 자릿수를 맞춘다. 결과의 각 자리는 두 수 중 정확히 하나의 같은 자리에 1이 있을 때 1이 된다. 예를 들어 $x=12$ , $y=26$ 이면 결과는 22이다.

입력

첫째 줄에 테스트 예제의 개수 $t$ 가 주어진다 ( $1 \le t \le 10^4$ ). 다음 $t$ 개 줄에 테스트 예제의 설명이 주어진다. 각 설명은 공백으로 구분된 두 수 $a$ 와 $n$ 으로 이루어진다 ( $1 \le a, n \le 10^{18}$ ).

출력

각 테스트 예제마다 구하는 $b$ 를 한 줄에 하나씩 출력한다.

예제1

예제 1
입력
```
3
10 5
3 2
98 100
```
예상 출력
```
0
1
6
```