题目描述

从前有个 Python 3 语言的程序是这样的：

ans = 0
n = int(input())
for i in range(1, n + 1):
	for j in range(1, n // i + 1):
		for k in range(1, j + 1):
			x = min(j, k)
			while not(j % x == 0 and k % x == 0):
				x = x - 1
			if x == 1:
				ans = (ans + 1) % 998244353
print(ans)

请注意：

• Python 3 语言的 range 所指的区间是是左闭右开的；
• // 代表舍去小数的除法

但是这个程序在 $n$ 不是很大的时候也会显得无能为力。所以你的任务就是优化这个程序的运行速度。

输入格式

第一行一个正整数 $T$ 表示数据组数。
接下来 $T$ 行每行一个正整数 $n$ 表示对程序输入的数。

输出格式

$T$ 行，对于每组数据输出程序应当输出的数。

3
3
1000000007
12345678909876543210

6
870325006
591139122

数据范围与提示

本题输入文件较大，请适当优化您的程序的读入速度。

本题共 $10$ 个测试点。各个测试点详细信息如下：