The Fibonacci sequence is defined as \(F[n]=F[n-1]+F[n-2]\). You have developed two sequences of numbers. The first sequence that uses the XOR operation instead of the addition method is called the Xoronacci number. It is described as follows:

The second sequence that uses the XNOR operation instead of the addition method is called the XNoronacci number. It is described as follows:

The first and second numbers of the sequence are as follows:

You have also defined the following constraint:

The minimum number of bits that that is used while representing the \(i^{th}\) term must be greater than equal to 3. It must be equal to the minimum number of bits that is required while respresenting the maximum pair (first number, second number) of the respective sequences.

Notes:

Your task is to determine the value of \(max(X(n),E(n))\).

Input format

• First line: \(t\) denoting the number of test cases
• Next \(t\) lines: Three integers \(a\), \(b\), and \(n\)

Output format

Print a single integer for each test case.

Constraints