积性函数之和（大） (Sum of Multiplicative Function (Large))

时间限制：30 秒

题目描述

给定一个积性函数 $f(x)$，满足 $f(p^e) = ae + bp$。输出 $\sum_{i=1}^{N} f(i) \mod 469762049$。

（使用 $469762049$ 而非 $998244353$，是因为它更易于计算非常长的卷积。）

共有 $T$ 组测试数据。

约束条件

• $1 \le T \le 10000$
• 若 $T = 1$，则 $1 \le N \le 10^{13}$；否则 $1 \le T\sqrt{N} \le 10^6$。
• $0 \le a, b < 469762049$

输入

T
N a b
N a b
⋮
N a b

样例

在提交之前，请确保样例输入能够足够快地运行。

10
1 2 3
2 2 3
3 2 3
4 2 3
5 2 3
6 2 3
7 2 3
8 2 3
9 2 3
10 2 3

1
9
20
30
47
135
158
170
183
319

1
100 4 5

181804

1
10000000000000 6 7

314120757