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.
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.
For each attack output the value of expression.
Explanation : Just evaluate the expression.
Language restriction Removed