该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述：

结果大家可能都知道了，人机大战第5场依然以人类失败而告终，李世石除了有一颗强大的心脏还有极强的自尊心。

他决定对上面的比赛进行一些改变：N个棋子排成一排，从1到N编号，一开始都是黑色朝上。接下来第1秒，把所有编号为1的倍数的棋子翻转；第2秒，把所有编号为2的倍数的棋子翻转；第3秒，把所有编号为3的倍数的棋子翻转，。。。，这样的操作一直持续了N秒。一直到这里都是跟上题一样。

接着李世石给阿法狗出了T个问题，每个问题都是给定两个整数Li，Ri(1<=Li<=Ri<=N)，问编号为Li到Ri的棋子中有多少个棋子被翻转了两次。阿法狗被这样的问题难住了，需要你的帮助。

输入： 第一行输入两个整数N(1<=N<=50,000,000),T(1<=T<=100,000)，分别表示棋子的数量和问题的数量。接下来T行，每行两个整数Li,Ri，对应着T次询问的区间。

输出： 对于每个问题输出一个整数表示对应的区间内被翻转两次的棋子数量。

样例输入：

10 3

3 6

2 5

4 9

样例输出：

2

3

2

数据范围：

20%的数据满足：N<=1,000,T<=1,000;

40%的数据满足：N<=10,000,T<=10,000;

60%的数据满足：N<=1,000,000,T<=100,000;

80%的数据满足：N<=5,000,000,T<=100,000;

100%的数据满足：N<=50,000,000,T<=100,000。