Chtholly gives you a sequence of length $n$ and $m$ queries. Each query asks for the number of divisors of the product of elements in a given range, modulo $19260817$.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing the sequence $a_i$.

The following $m$ lines each contain two integers $l$ and $r$, representing the query range.

Output

Output $m$ lines, each containing an integer representing the answer.

Examples

Input 1

5 5
64 2 18 9 100
1 5
2 4
2 3
1 4
3 4

Output 1

165
15
9
45
10

Note

Idea: will7101, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477

$1 \leq n, m \leq 10^5$, $1 \leq a_i \leq 10^9$.