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 :
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:
20171203 10:15:07
@Anupam: Thanks. 

anupamwadhwa:
20171203 03:36:58
Language restriction Removed 

wisfaq:
20171202 21:45:25
Nice problem.

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