{"code":"vaicprtspa","name":"[Variants] An interesting counting problem related to square product task A","description":"Given $q$ queries, you must find answer for each query.\r\n\r\nFor each query, you are given an positive integer $n\\ (1 \\leq n \\leq 10^{14})$.\r\n\r\nCount the number of pairs $(a, b)$ that satisfies:\r\n\r\n- $1 \\leq a < b \\leq n$\r\n- $a \\times b$ is a perfect square.\r\n\r\nSince the result can be large, output it under modulo $977555333311111$.\r\n\r\n

Input

\r\n\r\n- The first line contains a positive integer $q$.\r\n\r\n- The second line contains $q$ queries of positive integer $n_1, n_2, \\dots, n_q$.\r\n\r\n

Output

\r\n\r\n- In the **p-th** line, output a single number is the answer for query $n_p$ under modulo $977555333311111$.\r\n\r\n

Scoring

\r\n\r\n- **Subtask 1:** $16.67$% tests for $q = 1$ and $1 \\leq n \\leq 10^6$.\r\n\r\n- **Subtask 2:** $16.67$% tests for $q = 1$ and $1 \\leq n \\leq 10^{14}$.\r\n\r\n- **Subtask 3:** $16.67$% tests for $1 \\leq q \\leq 10$ and $1 \\leq n \\leq 10^{12}$.\r\n\r\n- **Subtask 4:** $16.67$% tests for $1 \\leq q \\leq 100$ and $1 \\leq n \\leq 10^{10}$.\r\n\r\n- **Subtask 5:** $16.67$% tests for $1 \\leq q \\leq 1000$ and $1 \\leq n \\leq 10^8$.\r\n\r\n- **Subtask 6:** $16.67$% tests for $1 \\leq q \\leq 10.000$ and $1 \\leq n \\leq 10^6$.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 1\r\n 1\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 0\r\n ```\r\n \r\n ??? warning \"Note\"\r\n There are no satisfied integer pair $(a, b)$ that $1 \\leq a < b \\leq 1$\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 2\r\n 10 25\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 4\r\n 16\r\n ```\r\n \r\n ??? warning \"Note\"\r\n In the first query, there are $4$ satisfied pairs: {$1, 4$}, {$1, 9$}, {$2, 8$}, {$4, 9$}.\r\n\r\n In the second query, there are $16$ satisfied pairs: {$1, 4$}, {$1, 9$}, {$1, 16$}, {$1, 25$}, {$2, 8$}, {$2, 18$}, {$3, 12$}, {$4, 9$}, {$4, 16$}, {$4, 25$}, {$5, 20$}, {$6, 24$}, {$8, 18$}, {$9, 16$}, {$9, 25$}, {$16, 25$}.\r\n\r\n!!! question \"Test 3\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 10\r\n 123456789 234567890 345678901 456789012 567890123 678901234 789012345 890123456 901234567 12345678\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 645956573\r\n 1273061974\r\n 1916838059\r\n 2571642223\r\n 3234719854\r\n 3903895878\r\n 4573092218\r\n 5191744600\r\n 5259963415\r\n 55955605\r\n ```","points":500.0,"partial":true,"time_limit":1.0,"memory_limit":1048576,"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}}