Trong Số học, Phi hàm Euler thường được kí hiệu là $\phi (n)$, là hàm số thể hiện số số nguyên dương không lớn hơn $n$ và nguyên tố cùng nhau với $n$. Trong bài này, ta có 2 số nguyên dương $l$, $r$, hãy tính giá trị $\phi (l\cdot (l+1)\cdot \dots \cdot r)$ $mod$ $M$.

Input

Dòng đầu gồm một số nguyên $M$ ($1\le M\le 998244353$).

Dòng thứ hai gồm 1 số nguyên $T$ ($1\le T\le 2\cdot {10}^5$) — số lượng bộ test.

$T$ dòng cuối cùng, mỗi dòng gồm $2$ số nguyên dương $l$, $r$ ($1\le l\le r\le {10}^6$) thể hiện một truy vấn.

Output

Gồm $T$ dòng là đáp án của mỗi truy vấn.

Scoring

Sample Input 1

998244353
3
1 2
2 5
5 7

Sample Output 1

1
32
48