Totient Summation Modulo 998244353

You are given T test cases. In each test case, two positive integers n and m are provided. Your task is to compute and output the value of

\( S = \left( \sum_{i=1}^{n} \sum_{j=1}^{m} \varphi(i \cdot j) \right) \bmod 998244353 \)

where \( \varphi(k) \) denotes Euler's totient function, which counts the number of integers in \([1, k]\) that are coprime with \( k \). For each test case, output the result on a new line.

If you are unfamiliar with the totient function, you may refer to its definition or standard sieve techniques to compute it efficiently.

inputFormat

The first line contains a single integer T, representing the number of test cases.

Each of the following T lines contains two space‐separated integers n and m.

outputFormat

For each test case, output a single line containing the value of

\( \left( \sum_{i=1}^{n} \sum_{j=1}^{m} \varphi(i\cdot j) \right) \bmod 998244353 \)

in the order the test cases are given.

sample

1
1 1

1