곱셈적 함수의 합

$f(p^e) = ae + bp$을 만족하는 곱셈적 함수 $f(x)$이 주어진다. $\displaystyle \sum_{i=1}^N f(i) \bmod 469762049$을 출력한다.
(매우 긴 합성곱을 계산하기가 더 쉽기 때문에 $998244353$ 대신 $469762049$을 사용한다.)
테스트 케이스는 $T$개이다.

제약 조건

• $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$

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

$f(p^e) = ae + bp$을 만족하는 곱셈적 함수 $f(x)$가 주어진다. $\displaystyle \sum_{i=1}^N f(i) \bmod 469762049$을 출력한다.