Infinity Tree

During your flight to the Link-Cut planet system, you got bored, so Lucy started telling you about nuclear physics! Specifically, how chain reactions work in the reactor on your ship.

Since the ship is unusual, the reactor is also unusual; it generates unique atoms, each with a unique characteristic, namely, a positive integer. When a new atom is generated, it picks the smallest unoccupied characteristic value (you can also think of it as the number one greater than the number of atoms that existed before it). Initially, the reactor produces one atom (with the number 1), after which the fission phase begins.

Atoms, in the order of their characteristics, start creating additional atoms. An atom with the characteristic $x$ will create $f(x)$ additional atoms. Here, $f(x)$ means the number of turned bits in the binary representation of the $x$, formally it could be defined as follows:

where $l(x)$ is the biggest non-negative integer $y$ such that $x$ is divisible by $2^y$.

These operations form a chain reaction tree. However, such a construction is not very stable, so breaks often occur. Each break can be defined by two atoms (specifically, their characteristics), and during each break, all connections on the path between these two atoms are destroyed. The reactor's task is to restore them, which is quite a complex process, so we will focus on one of its simplest parts, namely, calculating the required energy, which equals the number of destroyed connections.

A part of this tree

At this point, an asteroid hit your ship, and Lucy rushed off to fix the damage, giving you homework to write a program for calculating the energy. Since you are still learning, she simplified the task by stating that breaks will only occur between atoms whose characteristics are less than $n$.

The deadline is approaching, so don't procrastinate and do your homework.

Input

The first line contains two integers $n$ and $q$ $(2\le n\le 10^{15},1\le q\le 10^4)$ — the biggest characteristic value in each break and the number of breaks.

Each of the next $q$ lines contains two integers $v$ and $u$ $(1\le v\le n,1\le u\le n,v\ne u)$ — the characteristic value of two atoms between which the break takes place. Please note that each query is independent from others.

Output

For every break, you need to output the number of destroyed connections.

Examples

Scoring

1. ($24$ points): $n\le 100$;

2. ($23$ points): $n\le 10^6$;

3. ($59$ points): $n\le 10^{12}$;

4. ($19$ points): no additional constraints;