题目背景

A:“最近没题做了诶……”

B:“你有什么爱好?”

A:“数论,分块。”

于是就有了这道题。

题目描述

给出 $n,m$ 求下列式子的值 ：

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

输入格式

第一行一个整数 $T$，表示询问数。

后 $T$ 行每行两个整数 $n,m$ ,表示一个询问。

输出格式

对于每个询问，输出一行一个整数，表示答案。

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

提示

对于所有测试点， $T\leq 3\times 10^4,\ m\leq n\leq 5\times 10^4$。

测试点编号	$n,m\leq$	$T$	时限	特殊性质
#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