NTG - NT Games


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 :

IMAGE

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.


hide comments
wisfaq: 2017-12-03 10:15:07

@Anupam: Thanks.

anupamwadhwa: 2017-12-03 03:36:58

Language restriction Removed

wisfaq: 2017-12-02 21:45:25

Nice problem.
Please remove language restrictions.


Added by:anupamwadhwa
Date:2017-12-02
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Code Rush 2017, IIT (ISM), Dhanbad