很久以前的某一天，你发现了一个神奇的函数 $f(x)$，它满足很多神奇的性质：

1. $f(1)=1$。
2. $f(p^e)= ae + bp$（$p$ 为质数）。
3. $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$

提示

高效解决这个问题的方法较为冷门，收集了一些资料（https://github.com/yosupo06/library-checker-problems/issues/1118）供参考。