积性函数前缀和

【题目描述】

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

（这里使用 $469762049$ 而非 $998244353$，因为这样更容易计算很长的卷积。）

共有 $T$ 组测试数据。

【输入】

$T$
$N$ $a$ $b$
$N$ $a$ $b$
$\vdots$
$N$ $a$ $b$

【输出】

对每组测试数据，输出 $\displaystyle \sum_{i=1}^N f(i) \bmod 469762049$。

【输入样例】

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

【输入样例2】

1
100 4 5

【输出样例2】

181804

【输入样例3】

1
100000000000 6 7

【输出样例3】

22268225

【数据范围】

• $1 \leq T \leq 10000$
• 若 $T = 1$，则 $1 \leq N \leq 100000000000$；否则 $1 \leq T \sqrt{N} \leq 100000$。
• $0 \leq a, b \lt 469762049$

【来源】

Library Checker（yosupo06） sum_of_multiplicative_function