Points:
2300
Time limit:
5.0s
Memory limit:
977M
Input:
stdin
Output:
stdout
Cho số nguyên dương \(n\). Tính \(S=\sum\limits_{i=1}^{n}gcd(\left \lfloor{\sqrt[3]{i}}\right \rfloor ,i)\)
Trong đó:
-
\(gcd(a,b)\) - Thể hiện ước chung lớn nhất của hai số nguyên dương \(a\) và \(b\)
-
\(\left \lfloor{x}\right \rfloor\) - Thể hiện số nguyên lớn nhất và không vượt quá \(x\) (với \(x\) nguyên)
Input
-
Dòng thứ nhất chứa số \(t(1\le t\le 10)\) - Thể hiện số testcase
-
\(t\) dòng tiếp theo, mỗi dòng chứa số \(n(1\le n\le 10^{21})\)
Output
- Ứng với mỗi testcase, in ra \(S\) cần tìm. Vì \(S\) có thể rất lớn, nên ta cần lấy mod \(998244353\) trước khi in ra (Biết rằng: \(998244353\) là số nguyên tố.)
Scoring
-
\(10\%\) : \(1\le n\le 100\)
-
\(10\%\) : \(1\le n\le 1000000\)
-
\(20\%\) : \(1\le n\le 10^{9}\)
-
\(30\%\) : \(1\le n\le 10^{16}\)
-
\(30\%\) : Không có điều kiện gì
Example
Test 1
Input
3
180
526
267
Output
327
1069
522
Comments