题目描述

从前有个 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 $ 行，对于每组数据输出程序应当输出的数。

样例

input

3
3
1000000007
12345678909876543210

output

6
870325006
591139122

数据范围与提示

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

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