You are given the following pseudo code:

res = a
for i = 1 to k
    if i is odd
        res = res & b
    else
        res = res | b

You are also given the values of a, b, and k. Find the final value of res.

Input

• First line consists of a single integer, T, denoting the number of test cases.
• Each test case consists of 3 lines, each consisting of a single integer denoting a, b and k respectively.

Output
Print the final value of $res$ for each test case in a new line.

Constraints
$1 \le T \le 10^5$
$1 \le a, b, k \le 10^{18}$