CSES - HIIT Open 2016 - Fixed points
  • Time limit: 2.00 s
  • Memory limit: 256 MB

A fixed point for a function ff is a value xx such that f(x)=xf(x)=x.

In this task we focus on the following function: f(x)=((ax)b)mod264 f(x) = ((a \cdot x) \oplus b) \bmod 2^{64}The operator \oplus is the xor operator (written ^ in C++/Java).

Given aa and bb, can you find a fixed point for the function?

Input

The first input line contains an integer tt: the number of test cases.

After this, there are tt lines that describe the test cases. Each line contains two integers aa and bb.

All test cases have been generated so that aa and bb have been chosen uniformly randomly from the range 026410 \ldots 2^{64}-1.

Output

For each case, output a number 0x26410\leq x\leq 2^{64}-1 that is a fixed point for the function, or "-" if no such number exists.

If there are several possible solutions, you can output any of them.

Constraints

  • 1t1051 \le t \le 10^5
  • 0a,b26410\leq a, b\leq 2^{64}-1

Example

Input:

3
2 5
1 1
0 7

Output:

3
-
7

For example, in the first test case, f(3)=((23)5)mod264=3f(3)=((2\cdot3) \oplus 5) \bmod 2^{64}=3.