디리클레 역원과 누적 합

테스트 케이스가 $T$개 있다.

양의 정수 $N$이 주어졌을 때, $Q_N=\lbrace {\lfloor {N \over x} \rfloor \colon x \in \mathbb{Z}, 1 \leq x \leq N} \rbrace$로 정의한다.

$Q_N$의 원소를 오름차순으로 나열한 수열을 $(a_0,a_1,\ldots,a_{k-1})$로 나타낸다.

수열 $f \colon \mathbb{N} \to \mathbb{F} _ {998244353}$에 대해, 각 $x \in Q_N$까지의 누적 합을 다음과 같이 정의한다.

이때, $g$를 Dirichlet Convolution에 대한 $f$의 역원이라고 하자. 즉, $\sum_{ij=n}f(i)g(j)=\delta_{1,n}$이 성립한다. 각 $x \in Q_N$에 대해 누적 합

을 계산한다.

제약 조건

• $1 \leq N \leq 1000000000000$
• $0 \leq f_x < 998244353$
• $f_1\neq 0$
• $T>1$이면, $T=10000$이며 각 $N=1,2,\ldots,10000$마다 정확히 하나의 테스트 케이스가 있다.

$T$
$case_1$
$\vdots$
$case_T$

각 테스트 케이스는 다음 형식으로 주어진다.

$N$
$f_{a_0}$ $f_{a_1}$ $\ldots$ $f_{a_{k-1}}$

$g_{a_0}$ $g_{a_1}$ $\ldots$ $g_{a_{k-1}}$