Description

Hong is a girl who likes to daydream. She thinks the dependence value of two positive integers $i, j$ is $\operatorname{lcm}(i,j)^{\operatorname{lcm}(i,j)}$. She defines the product of the dependence values of all $i, j$ satisfying $l \le i \le r, l \le j \le r$ as the obstacle value of two positive integers $l, r$. Now she gives you a positive integer $n$, and asks you $t$ queries. In each query, you are given two positive integers $l, r$ satisfying $1 \le l \le r \le n$. You need to output the obstacle value $ans \bmod{32465177}$.

Input Format

The first line contains two positive integers $t, n$.

The next $t$ lines each contain two positive integers $l_i, r_i$, representing one query.

Output Format

For each query, output one integer representing the answer.

3 7
1 3
2 3
7 7

21072733
12145631
823543

Hint

Brief statement:

Given $l, r$, compute $\prod\limits_{i=l}^{r}\prod\limits_{j=l}^{r}\operatorname{lcm}(i,j)^{\operatorname{lcm}(i,j)} \bmod{32465177}$. There are multiple queries.

Sample explanation:

For the 1st query, $ans = 1^1 \times (2^2)^3 \times (3^3)^3 \times (6^6)^2$, and $ans \bmod{32465177} = 21072733$.

For the 2nd query, $ans = 2^2 \times 3^3 \times (6^6)^2$, and $ans \bmod{32465177} = 12145631$.

For the 3rd query, $ans = 7^7 = 823543$.

Constraints:

For $30\%$ of the testdata, $1 \le n \le 10^3, t = 1$.

For $60\%$ of the testdata, $1 \le n \le 10^5, t = 1$.

For $100\%$ of the testdata, $1 \le n \le 10^6, 1 \le t \le 10, 1 \le l_i \le r_i \le n$.

Translated by ChatGPT 5