Taplu was taught that Binary OR operator is analogous to addition in mathematics. He wondered that there would be many such pairs (x, y) such that:

    x + y = x | y ('|' represents Binary OR)

He then started calculating all values of y of a given x. There can be many possible solutions, so Taplu went upto Abhishar to help him find the kth smallest possible solution. Given x and k, help Abhishar to find the kth smallest positive value of y.

Input

First line contains the number of test cases T(1 <= T <= 10).

Every test case contains two numbers x and k (1 <= x, k <= 2*10^9)

Output

For every test case output the required number y.

Example

Input:
1
3 1

Output:
4