Нескінченне дерево

Під час польоту до планетарної системи Link-Cut вам стало нудно, і Люсі почала розповідати вам про ядерну фізику. Конкретно, про те, як працюють ланцюгові реакції в реакторі вашого корабля.

Оскільки корабель незвичайний, то й реактор теж незвичайний; він генерує унікальні атоми, кожен з унікальною характеристикою, тобто з додатнім цілим числом. При генерації нового атома вибирається найменше доступне значення характеристики (ви також можете думати про це як про число, на одиницю більше, ніж кількість атомів, які існували раніше). Спочатку реактор виробляє атом (з номером 1), після чого починається фаза розщеплення.

Атоми, в порядку їх характеристик, починають створювати додаткові атоми. Атом з характеристикою $x$ створить $f(x)$ додаткових атомів. Тут $f(x)$ означає кількість встановлених бітів у двійковому представленні $x$, формально це можна визначити наступним чином:

де $l(x)$ - найбільше невід'ємне ціле $y$ таке, що $x$ ділиться на $2^y$.

Ці операції формують дерево ланцюгової реакції. Однак така конструкція не дуже стійка, тому розриви відбуваються часто. Кожен розрив можна визначити двома атомами (конкретно, їх характеристиками), і під час кожного розриву всі з'єднання на шляху між цими двома атомами руйнуються. Задача реактора - відновити їх, що є досить складним процесом, тому ми зосередимося на одній з його найпростіших частин, тобто на обчисленні потрібної енергії, яка дорівнює кількості руйнувань з'єднань.

Частина цього дерева

У цей момент ваш корабель був атакований астероїдом, і Люсі поспішила виправити збиток, давши вам домашнє завдання написати програму для обчислення енергії. Оскільки ви все ще вчитеся, вона спростила завдання, стверджуючи, що розриви будуть відбуватися тільки між атомами, чиї характеристики менше $n$.

Наближається дедлайн , тому не зволікайте і виконуйте своє завдання.

Вхідні дані

Перший рядок містить два цілі числа $n$ і $q$ $(2\le n\le 10^{15},1\le q\le 10^4)$ - найбільше значення характеристики в кожному розриві та кількість розривів.

Кожен з наступних $q$ рядків містить два цілі числа $v$ і $u$ $(1\le v\le n,1\le u\le n,v\ne u)$ - значення характеристики двох атомів, між якими відбувається розрив. Зверніть увагу, що кожний запит незалежний від інших.

Вихідні дані

Для кожного розриву виведіть кількість руйнуваних з'єднань.

Приклади

Оцінювання

1. ($24$ бали): $n\le 100$;

2. ($23$ бали): $n\le 10^6$;

3. ($59$ балів): $n\le 10^{12}$;

4. ($19$ балів): Без додаткових обмежень;