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.


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

hide comments
2019-02-03 15:26:22
AC in one go:)
2017-12-03 10:15:07 wisfaq
@Anupam: Thanks.
2017-12-03 03:36:58
Language restriction Removed
2017-12-02 21:45:25 wisfaq
Nice problem.
Please remove language restrictions.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.