Problem Description

Kazari is too bored this summer holiday, she decides to play with formulas.
First of all, she comes up with two positive integers $N, K$.
She loves power, therefore she builds a sequence $a$ where $a_i = i ^ K$ $(1 \le i \le N)$.
She loves summation, therefore she calculate the partial sum of $a$ as $s$, i.e. $s_i = \sum_{j \le i} {a_j}$ $(1 \le i \le N)$.
She also loves coprimes, therefore she calculate the sum of elements in $s$ whose index $i$ is coprime to $N$, i.e. $v = \sum_{1 \le i \le N, \gcd(i, N) = 1} {s_i}$
Your task is to work out $v$. Since the answer is too large, print it modulo $998244353$.

Input

The first line of the input contains an integer $T$ denoting the number of test cases.
Each test case starts with a positive integer $K$ $(K \le 10 ^ 5, \sum{K} \le 10 ^ 6)$.
The second line contains a positive integer $m$ $(m \le 20)$, indicating the number of distinct primes of $N$.
Each of next $m$ lines contains two positive integers $p_i, a_i$ where $p_i$ is a prime $(p_i, a_i \le 10 ^ 9, p_i < p_{i + 1})$.
$$N = \prod_{i = 1} ^ {m} {p_i ^ {a_i}}$$

Output

For each test case, print an integer representing the answer modulo $998244353$.

2
1
2
2 1
3 1
233
1
23333 1

16
32727388