很久以前的某一天，你发现了一个神奇的函数 $f(x)$，它满足很多神奇的性质：
- $f(1)=1$。
- $f(p^e)= ae + bp$（$p$ 为质数）。
- $f(xy)=f(x)f(y)$（$x$ 与 $y$ 互质）。
令 $S(m)=\sum\limits_{i=1}^m f(i) \bmod 469762049$，你需要对于 $i=1,2,3,\cdots,n$ 求出 $S(\lfloor n/i\rfloor)$，去重并输出异或和。
注：为鼓励探索新做法，本题使用了精心挑选的数 $469762049$。域 $\mathbb{Z} / 469762049 \mathbb{Z}$ 有 $2^{26}$ 次本原单位根，$3$ 是它的一个原根。
输入格式
第一行一个正整数 $T$，表示有 $T$ 组测试数据。
接下来 $T$ 行，第 $i$ 行 $3$ 个正整数 $n_i$，$a_i$，$b_i$，其中 $a_i$ 和 $b_i$ 为 $f(x)$ 的性质 2 中的参数 $a$ 和 $b$。
输出格式
输出 $T$ 行，第 $i$ 行一个非负整数，表示去重后的 $\left\{S(\lfloor n/i\rfloor)\right\}_{i\in[1,n_i]}$ 的异或和。
样例数据
样例 1 输入
1
6 2 2样例 1 输出
90样例 1 解释
去重后的集合为 $\{1, 7, 15, 83\}$，异或和为 $90$。
样例 2 输入
1
233333 29 31样例 2 输出
227062462样例 3 输入
1
9876543210 98765 43210样例 3 输出
78615365子任务
$1 \leq T \leq 10^4$。
$0 \leq a_i, b_i < 469762049$。
当 $T = 1$ 时，$1 \leq n \leq 10^{13}$，否则 $1 \leq T \sqrt{\max_{i=1}^T n_i} \leq 10^6$