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

3
180
526
267

327
1069
522