题目描述
Problem Description
Given \( n, m \), compute the value of the following expression:
\[ \sum_{i=1}^n \sum_{j=1}^m \varphi\left(\frac{{\rm lcm}(i,j)}{\gcd(i,j)}\right) \bmod 23333 \]
Input Format
The first line contains an integer \( T \), representing the number of queries.
The next \( T \) lines each contain two integers \( n, m \), representing a query.
Output Format
For each query, output a single line containing an integer, which is the answer.
Sample Input and Output
Sample Input #1
5
10 10
20 20
30 30
40 40
50 50
Sample Output #1
768
13312
16218
7160
9031
Sample Input #2
3
5 4
20 15
100 88
Sample Output #2
52
7572
21475
Notes/Hints
For all test cases, \( T \leq 3 \times 10^4, m \leq n \leq 5 \times 10^4 \).
| Test Case Number | \( n, m \leq \) | \( T \) | Time Limit | Special Properties |
|---|---|---|---|---|
| #1~2 | 100 | 100 | 1s | |
| #3~4 | 2000 | $3 \times 10^4$ | 1s | |
| #5~6 | $3 \times 10^4$ | 5000 | 2s | |
| #7~8 | 5 \times 10^4 | 3 \times 10^4 | 2s | \( n = m \) |
| #9~10 | $5 \times 10^4$ | $3 \times 10^4$ | 2s |
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分
样例输入
5
10 10
20 20
30 30
40 40
50 50
样例输出
768
13312
16218
7160
9031