Katniss Everdeen after participating in Hunger Games now wants to participate in Number Theory Games.

As she begins President Snow provides her a number k. Then, she has to defend t back to back attacks from Haymitch Abernathy for practice. In each attack Haymitch Abernathy gives two numbers l and r, for defense she has to compute :

As she is new to number theory, help her by computing given expression.

Input

First line contain an integer, i.e. k.

Second line contain an integer, i.e. t.

Each of next t lines contain two integers, i.e. l and r.

Constraints

1 ≤ k ≤ 10⁵

1 ≤ t ≤ 10⁵

1 ≤ l ≤ r ≤ 10⁵

Output

For each attack output the value of the expression.

Example

Input:
1
1
1 5
Output:
26