Description

Given $n,m$, find the value of the following expression:

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^m \varphi\left(\dfrac{{\rm lcm}(i,j)}{\gcd(i,j)}\right) \bmod 23333$$

Input Format

The first line contains an integer $T$, which denotes the number of queries.

The next $T$ lines each contain two integers $n,m$, representing one query.

Output Format

For each query, output one integer per line, which is the answer.

5
10 10
20 20
30 30
40 40
50 50

768
13312
16218
7160
9031

3
5 4
20 15
100 88

52
7572
21475

Hint

For all test cases, $T\leq 3\times 10^4,\ m\leq n\leq 5\times 10^4$.

Test Point ID	$n,m\leq$	$T$	Time Limit	Special Property
#1~2	$100$		$\texttt{1s}$
#3~4	$2000$	$3\times 10^4$
#5~6	$3\times 10^4$	$5000$	$\texttt{2s}$
#7~8	$5\times 10^4$	$3\times 10^4$		$n=m$
#9~10

Translated by ChatGPT 5