Katniss Everdeen after participating in Hunger Games now wants to participate in NT Games (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 Format

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 & r.

Constraints

1<=k<=10^5

1<=t<=10^5

1<=l<=10^5

l<=r<=10^5

Output Format

For each attack output the value of expression.

Sample Input

1

1

1 5

Sample Output

26

Explanation : Just evaluate the expression.