{"code":"vaicprtspb","name":"[Variants] An interesting counting problem related to square product task B","description":"Given $q$ queries, you must find answer for each query.\r\n\r\nFor each query, you are given an positive integer $n, k\\ (1 \\leq k \\leq n \\leq 10^{13})$.\r\n\r\nCount the number of arrays $a[]$ of size $k$ that satisfies:\r\n\r\n- $1 \\leq a_1 < a_2 < \\dots < a_k \\leq n$\r\n- $a_i \\times a_{i+1}$ is a perfect square $\\forall 1 \\leq i < n$\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 single integer $\\lambda$ is the number of this subtask.\r\n\r\n- The second line contains a positive integer $q$.\r\n\r\n- The next $q$ lines, the $pth$ query will contain $2$ positive integers $k, n$.\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, k_p)$ under modulo $977555333311111$.\r\n\r\n

Scoring

\r\n\r\n- **Subtask 1:** $10.00$% tests $\\lambda = 1$ for $1 \\leq q \\leq 100.000$ queries of $1 \\leq k \\leq \\log_2(n) \\leq n \\leq \\large \\frac{10^{11}}{q}$\r\n\r\n- **Subtask 2:** $10.00$% tests $\\lambda = 2$ for $1 \\leq q \\leq 100$ queries of $1 \\leq k \\leq n \\leq 100$.\r\n\r\n- **Subtask 3:** $10.00$% tests $\\lambda = 3$ for $1 \\leq q \\leq 10$ queries of $1 \\leq k \\approx \\sqrt{n} \\leq n \\leq 10^{10}$\r\n\r\n- **Subtask 4:** $10.00$% tests $\\lambda = 4$ for $1 \\leq q \\leq 10$ queries of $1 \\leq k \\approx \\sqrt[3]{n} \\leq n \\leq 10^{10}$\r\n\r\n- **Subtask 5:** $10.00$% tests $\\lambda = 5$ for $1 \\leq q \\leq 100$ queries of $1 \\leq k \\leq n \\leq 2^{22}$ and $k, n$ are power of two.\r\n\r\n- **Subtask 6:** $10.00$% tests $\\lambda = 6$ for $1 \\leq q \\leq 1000$ queries of $1 \\leq k \\approx \\sqrt{n} \\leq n \\leq 10^{7}$\r\n\r\n- **Subtask 7:** $10.00$% tests $\\lambda = 7$ for $1 \\leq q \\leq 1000$ queries of $1 \\leq k \\approx \\sqrt[3]{n} \\leq n \\leq 10^{7}$\r\n\r\n- **Subtask 8:** $10.00$% tests $\\lambda = 8$ for $1 \\leq q \\leq 10.000$ queries of $1 \\leq k \\approx \\sqrt{n} \\leq n \\leq 10^{4}$\r\n\r\n- **Subtask 9:** $10.00$% tests $\\lambda = 9$ for $1 \\leq q \\leq 10.000$ queries of $1 \\leq k \\approx \\sqrt[3]{n} \\leq n \\leq 10^{4}$\r\n\r\n- **Subtask 10:** $10.00$% tests $\\lambda = 10$ for $q = 1$ query of $1 \\leq k \\leq n \\leq 10^{13}$\r\n\r\n**Intended solution:** $O(\\sqrt{n} \\log \\log \\sqrt{n})$ per query.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 10\r\n 1\r\n 2 1\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 2\r\n ```\r\n \r\n ??? warning \"Note\"\r\n There are $2$ satisfied arrays {$1$}, {$2$}\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 2\r\n 3\r\n 10 2\r\n 25 2\r\n 27 3\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 4\r\n 16\r\n 12\r\n ```\r\n \r\n ??? warning \"Note\"\r\n In the first query, there are $4$ satisfied arrays: {$1, 4$}, {$1, 9$}, {$2, 8$}, {$4, 9$}.\r\n\r\n In the second query, there are $16$ satisfied arrays: {$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 In the third query, there are $12$ satisfied arrays: {$1, 4, 9$}, {$1, 4, 16$}, {$1, 4, 25$}, {$1, 9, 16$}, {$1, 9, 25$}, {$1, 16, 25$}, {$2, 8, 18$}, {$3, 12, 27$}, {$4, 9, 16$}, {$4, 9, 25$}, {$4, 16, 25$}, {$9, 16, 25$}.\r\n\r\n\r\n!!! question \"Test 3\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 1\r\n 10\r\n 123456789 1\r\n 234567890 2\r\n 345678901 3\r\n 456789012 4\r\n 567890123 5\r\n 678901234 6\r\n 789012345 7\r\n 890123456 8\r\n 901234567 9\r\n 12345678 10\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 123456789\r\n 1273061974\r\n 2324814700137\r\n 497809922458658\r\n 162321859768410\r\n 154368725290449\r\n 443251450189935\r\n 281974354563468\r\n 117720773712544\r\n 148331601579738\r\n ```","points":600.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}}