{"code":"vipgcd","name":"Tính tổng với GCD","description":"Cho số nguyên dương $n$. Tính $S=\\sum\\limits_{i=1}^{n}gcd(\\left \\lfloor{\\sqrt[3]{i}}\\right \\rfloor ,i)$ \r\n\r\nTrong đó: \r\n\r\n + $gcd(a,b)$ - Thể hiện ước chung lớn nhất của hai số nguyên dương $a$ và $b$\r\n\r\n + $\\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)\r\n\r\n

Input

\r\n\r\n+ Dòng thứ nhất chứa số $t(1\\le t\\le 10)$ - Thể hiện số testcase\r\n\r\n+ $t$ dòng tiếp theo, mỗi dòng chứa số $n(1\\le n\\le 10^{21})$\r\n\r\n

Output

\r\n\r\n+ Ứ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ố.)\r\n\r\n

Scoring

\r\n\r\n+ $10\\%$ : $1\\le n\\le 100$\r\n\r\n+ $10\\%$ : $1\\le n\\le 1000000$\r\n\r\n+ $20\\%$ : $1\\le n\\le 10^{9}$\r\n\r\n+ $30\\%$ : $1\\le n\\le 10^{16}$\r\n\r\n+ $30\\%$ : Không có điều kiện gì\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 3\r\n 180\r\n 526\r\n 267\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 327\r\n 1069\r\n 522\r\n ```","points":2300.0,"partial":false,"time_limit":5.0,"memory_limit":1000000,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}