A long time ago, you discovered a magical function $f(x)$ that satisfies many magical properties:

1. $f(1)=1$.
2. $f(p^e)= ae + bp$ (where $p$ is a prime number).
3. $f(xy)=f(x)f(y)$ (where $x$ and $y$ are coprime).

Let $S(m)=\sum\limits_{i=1}^m f(i) \bmod 469762049$. You need to calculate $S(\lfloor n/i\rfloor)$ for $i=1,2,3,\cdots,n$, then output the XOR sum of the unique values.

Note: To encourage the exploration of new methods, this problem uses the carefully chosen number $469762049$. The field $\mathbb{Z} / 469762049 \mathbb{Z}$ has a $2^{26}$-th primitive root of unity, and $3$ is a primitive root of this field.

Input

The first line contains a positive integer $T$, representing the number of test cases.

Each of the next $T$ lines contains three positive integers $n_i$, $a_i$, and $b_i$, where $a_i$ and $b_i$ are the parameters $a$ and $b$ from property 2 of $f(x)$.

Output

Output $T$ lines, where the $i$-th line contains a non-negative integer representing the XOR sum of the unique values in the set $\left\{S(\lfloor n/i\rfloor)\right\}_{i\in[1,n_i]}$.

Examples

Input 1

1
6 2 2

Output 1

90

Note 1

The set of unique values is $\{1, 7, 15, 83\}$, and their XOR sum is $90$.

Input 2

1
233333 29 31

Output 2

227062462

Input 3

1
9876543210 98765 43210

Output 3

78615365

Subtasks

$1 \leq T \leq 10^4$.

$0 \leq a_i, b_i < 469762049$.

When $T = 1$, $1 \leq n \leq 10^{13}$; otherwise, $1 \leq T \sqrt{\max_{i=1}^T n_i} \leq 10^6$.

Note

Efficient methods to solve this problem are relatively uncommon. Some resources (https://github.com/yosupo06/library-checker-problems/issues/1118) have been collected for reference.