Серсея и Джейме украли из запасов Бобрового Утёса n золотых монет. Пока Тайвин не заметил пропажи, они решили сыграть в следующую игру.
Игра состоит из q раундов. В начале каждого раунда все n монет лежат в одной кучке. Игроки по очереди берут из кучки не менее ki и не более li монет (ki ≤ li, i — номер раунда). Проигрывает тот игрок, который не может сделать ход.
Серсея и Джейме определили для каждого из q раундов пары чисел (ki, li). Поскольку того, кто ходит первым, Серсея и Джейме определяют подбрасыванием монетки, они не видят большого смысла выяснять, кто из них в каком раунде победит. Им интересна максимально возможная длительность каждого раунда при условии, что каждый из них играет оптимально, то есть стремится выиграть. Длительность раунда определяется суммарным количеством ходов Серсеи и Джейме.
Ваша задача — определить максимально возможную длительность каждого раунда игры.
В первой строке содержатся целые числа n и q — количество монет и количество раундов соответственно (1 ≤ n ≤ 106, 1 ≤ q ≤ 105).
В каждой из следующих q строк содержится пара целых чисел ki и li 
— минимальное и максимальное количество монет, которое игрок может взять за один ход в i-м раунде.
Выведите q целых чисел через пробел. Число на позиции i должно быть равно максимально возможной длительности i-го раунда.
10 2
1 1
5 6
10 1
