XORVAL - Its a Bit Game

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

Added by:Rajesh Kumar
Date:2014-09-21
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2018-08-20 16:07:36
What garfield said. Nice one.
2015-06-08 01:01:22 anon
deserves better than tutorial
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.