Given \(q\) queries, you must find answer for each query.

For each query, you are given an positive integer \(n, k\ (1 \leq k \leq n \leq 10^{13})\).

Count the number of arrays \(a[]\) of size \(k\) that satisfies:

• \(1 \leq a_1 < a_2 < \dots < a_k \leq n\)
• \(a_i \times a_{i+1}\) is a perfect square \(\forall 1 \leq i < n\)

Since the result can be large, output it under modulo \(977555333311111\).

Input

• The first line contains a single integer \(\lambda\) is the number of this subtask.

• The second line contains a positive integer \(q\).

• The next \(q\) lines, the \(pth\) query will contain \(2\) positive integers \(k, n\).

Output

• In the p-th line, output a single number is the answer for query \((n_p, k_p)\) under modulo \(977555333311111\).

Scoring

• 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}\)

• Subtask 2: \(10.00\)% tests \(\lambda = 2\) for \(1 \leq q \leq 100\) queries of \(1 \leq k \leq n \leq 100\).

• 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}\)

• 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}\)

• 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.

• 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}\)

• 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}\)

• 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}\)

• 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}\)

• Subtask 10: \(10.00\)% tests \(\lambda = 10\) for \(q = 1\) query of \(1 \leq k \leq n \leq 10^{13}\)

Intended solution: \(O(\sqrt{n} \log \log \sqrt{n})\) per query.

Example

10
1
2 1

2

2
3
10 2
25 2
27 3

4
16
12

1
10
123456789 1
234567890 2
345678901 3
456789012 4
567890123 5
678901234 6
789012345 7
890123456 8
901234567 9
12345678 10

123456789
1273061974
2324814700137
497809922458658
162321859768410
154368725290449
443251450189935
281974354563468
117720773712544
148331601579738