SP33777 NTG - NT Games
Description
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
Input Format
N/A
Output Format
N/A