human
Can you provide a Python program to find them given the following:
Cengiz recently learned Fibonacci numbers and now he is studying different algorithms to find them. After getting bored of reading them, he came with his own new type of numbers that he named XORinacci numbers. He defined them as follows: 

  * f(0) = a.

  * f(1) = b.

  * f(n) = f(n-1) ⊕ f(n-2) when n > 1, where ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 


You are given three integers a, b, and n, calculate f(n).

You have to answer for T independent test cases.

Input

The input contains one or more independent test cases.

The first line of input contains a single integer T (1 ≤ T ≤ 10^3), the number of test cases.

Each of the T following lines contains three space-separated integers a, b, and n (0 ≤ a, b, n ≤ 10^9) respectively.

Output

For each test case, output f(n).

Example

Input

3
3 4 2
4 5 0
325 265 1231232

Output

7
4
76

Note

In the first example, f(2) = f(0) ⊕ f(1) = 3 ⊕ 4 = 7.
assistant
#Here is Python program to find them.

#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

def main():
    t = int(input())

    for _ in range(t):
        a, b, n = map(int, input().split())
        f3 = a ^ b

        print([a, b, f3][n % 3])

# region fastio

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")

def print(*args, **kwargs):
    """Prints the values to a stream, or to...