Trong Số học, Phi hàm Euler thường được kí hiệu là ~φ(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ị ~φ(l \cdot (l + 1)\cdot \ldots \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