Problem Description

Little Y can’t help himself learning number theory. However, math is too hard for him. He was beaten by SPOJ AFS3 and felt down. So here is a simple math problem. Let σk(n) be the following definition:

$$
\sigma_k(n) = \sum_{d|n} d^k
$$

For example, when k = 0, this function is known as the count of divisors of n. And when k = 1, this function is known as the sum of divisors of n.

Now he wants to calculate the following fomula for given a and b.

$$
\left( \left( \sum_{i=1}^n \sigma_a(i) \right) \oplus \left( \sum_{i=1}^n \sigma_b(i) \right) \right) \mod 2^{64}
$$

where $\oplus$ means the bitwise exclusive or.

Input

The first line contains an integer T (1 ≤ T ≤ 15) denoting the count of testcase.

For each testcase, one line containing three integer a,b and n.

To be much simpler,it is guaranteed that 0 ≤ a,b < 4 and 1 ≤ n ≤ $10^{12}$.Then you can solve this problem without either interpolation or SPOJ DIVCNT1.

Output

For each testcase, one line containing the value.

2
0 1 4
2 3 2

7
12