G. Genome Evolution
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are a close friend of Dr. G, a bioinformatics scientist working at Phitron. Dr. G is studying the evolution of a synthetic genome in a controlled laboratory environment. Each genome is represented by a non-negative integer, where each bit in its binary representation corresponds to the presence or absence of a specific genetic marker.

The genome evolves over discrete time steps according to the following rules:

  • At time step $$$1$$$, the genome has value $$$a$$$.
  • At time step $$$2$$$, the genome has value $$$b$$$.
  • For every time step $$$t \ge 3$$$, the genome is formed by examining the genomes at time steps $$$t-1$$$ and $$$t-2$$$, and constructing a new genome that contains only those genetic markers that appear in both of them.

Dr. G has been manually checking whether the genome sequences evolve correctly, but this task has become extremely tedious and time-consuming. To help your friend, you decide to write a program that determines the genome value at a given time step $$$t$$$.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$), the number of independent experiments.

Each of the next $$$T$$$ lines contains three integers $$$a$$$, $$$b$$$, and $$$t$$$ ($$$0 \le a, b \le 10^6$$$, $$$1 \le t \le 10^{8}$$$), where:

  • $$$a$$$ is the genome value at time step $$$1$$$,
  • $$$b$$$ is the genome value at time step $$$2$$$,
  • $$$t$$$ is the time step to be evaluated.
Output

For each experiment, output a single integer — the genome value at time step $$$t$$$.

Example
Input
3
11 13 1
11 13 2
11 13 3
Output
11
13
9
Note

In this example, the initial genome values are $$$a = 11$$$ and $$$b = 13$$$.

  • For $$$t = 1$$$, the genome value is defined as $$$a$$$, so the output is $$$11$$$.
  • For $$$t = 2$$$, the genome value is defined as $$$b$$$, so the output is $$$13$$$.
  • For $$$t = 3$$$, the genome is constructed by keeping only the genetic markers that appear in both genomes at time steps $$$1$$$ and $$$2$$$.

The binary representations of the initial genomes are:

  • $$$11 = (1011)_2$$$
  • $$$13 = (1101)_2$$$
Only the leftmost and the rightmost markers are present in both genomes. Therefore, the resulting genome value at time $$$t=3$$$ is: $$$(1001)_2 = 9$$$