题目描述

给出 $n,m$，求

$ \sum_{i=1}^n\sum_{j=1}^m\varphi(ij) \pmod{998244353} $

一共有 $T$ 组数据。

输入格式

第一行包含一个正整数 $T$，表示数据组数。
接下来 $T$ 行，每行包含两个正整数 $n, m$。

输出格式

输出 $T$ 行，每行一个正整数。

样例

输入

1
3 4

输出

29

数据范围与提示

• 对于 $40\%$ 的数据，$T=1$；
• 对于 $50\%$ 的数据，$1\leq T\leq 1000$；
• 对于另 $10\%$ 的数据，$n = m$；
• 对于 $100\%$ 的数据，$1\leq T,n,m\leq 10^5$。