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

写在前面

看吧，星星只有在夜里才璀璨夺目啊。
--《四月是你的谎言》

这是本蒟蒻第一次为大家出题，也是出过的第一道题。

lgy在这里祝大家都能迅速切掉这道大水题。

PS：题目并不难。

题目背景

“明天就要返校取成绩了吗”
不知不觉间，lgy的初中生活就要结束了啊
“这么有纪念意义的日子 当然要好好地放松<del>颓废</del>一下啊”
于是，lgy开始了初中的最后一次酒馆之行，可是，这次有点不一样哦
“今晚累得够呛，但只要有客人来玩，我都欢迎！”lgy的耳边再次响起了酒馆老板爽朗大方的声音。

题目描述

和旅店老板互相问好之后，lgy了解到今晚酒馆客人很多，所以需要lgy的帮助。正直大方的lgy爽快地答应了。

酒馆老板需要lgy做的事情非常简单，只需要往酒杯里倒酒就可以了。

桌子上有N个空酒杯排成一排，这些酒杯都是奥数酒杯。当客人坐到酒杯面前的位置上时，lgy就需要把这个酒杯中倒满酒。客人总是会成群结队地进入旅馆，并且坐在连续的几个座位上。总共有M群客人。每当有新的客人到来，原先坐在这个位置上的人就会知趣地离开。当一个奥术酒杯被倒入酒之后，今晚就会变成普通的酒杯。lgy每为一群人倒酒，老板都会给lgy一些奥术之尘作为报酬。lgy每次倒酒后能获得与奥术酒杯的数量相同的奥术之尘。即这次倒完酒之后，每有一个奥术酒杯，lgy就可以获得一杯奥术之尘。

lgy想要合成一套最新的毒瘤卡组，但是数学很差的他不知道酒馆老板每次送给他多少杯奥术之尘，所以lgy想请擅长编程的你来告诉他，他为这M群客人倒酒，每次都获得了几罐奥术之尘。

输入描述

第1行共包括2个正整数，分别为N,M。
接下来M行每行两个正整数L,R。

输出描述

一共输出M行，每行一个非负整数，表示lgy为这群客人倒酒后获得的奥术之尘罐数。

输入样例

10 3
3 5
2 8
1 5

输出样例

7
3
2

数据范围及提示

对于30%的数据，满足N，M<=5,000。

对于60%的数据，满足N，M<=100,000。

对于100% 的数据，满足1<=L<=R<=N<=500,000，1<=M<=500,000。