G. Grade 2
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Kotsuki the Cat, together with FuuFuu and Pico, lives in the KFP apartment. As a teacher, Kotsuki needs to go to school every day to give lessons. One day, Kotsuki gives a math lesson to some grade 2 students in primary school, covering the following topics:

  • Coprime: Two integers are coprime if the only positive integer that is a divisor of both of them is $$$1$$$.
  • Bitwise XOR ($$$\oplus$$$): Bitwise XOR is a binary operation that takes two integers and performs the logical exclusive OR operation on each pair of corresponding bits of their binary forms. The result in each will be $$$1$$$ if only one of the bits is $$$1$$$, but will be $$$0$$$ if both are $$$0$$$ or both are $$$1$$$. For example, $$$5\oplus3=(101)_2\oplus(011)_2=(110)_2=6$$$.

After class, Kotsuki assigns homework to the students:

  • Given an integer $$$x$$$, for different intervals $$$[l, r]$$$, please calculate the number of integers $$$k$$$ within the interval satisfying $$$kx \oplus x$$$ and $$$x$$$ are coprime. Formally, please calculate $$$$$$\sum_{k=l}^r[\text{gcd}(kx \oplus x,x)=1]$$$$$$ where $$$\text{gcd}(a,b)$$$ denotes the greatest common divisor of $$$a$$$ and $$$b$$$, and $$$[\ ]$$$ denotes the Iverson bracket $$$[P]={\begin{cases}1&{\text{if }}P{\text{ is true}}\\0&{\text{otherwise}}\end{cases}}$$$. Specially, $$$\text{gcd}(0,a)=a$$$.

Can you solve this grade 2 homework?

Input

The first line contains two integers $$$x$$$ ($$$1 \le x \le 10^6$$$) and $$$n$$$ ($$$1 \le n \le 10^5$$$), where $$$n$$$ indicates the number of intervals.

Each of the following $$$n$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^{12}$$$), indicating an interval $$$[l,r]$$$.

Output

For each interval, output the answer in a single line.

Example
Input
15 2
1 4
11 4514
Output
2
2252
Note

When $$$x=15$$$,

  • $$$k=1$$$, $$$\text{gcd}(kx \oplus x,x)=\text{gcd}(15\oplus15,15)=\text{gcd}(0,15)=15$$$
  • $$$k=2$$$, $$$\text{gcd}(kx \oplus x,x)=\text{gcd}(30\oplus15,15)=\text{gcd}(17,15)=1$$$
  • $$$k=3$$$, $$$\text{gcd}(kx \oplus x,x)=\text{gcd}(45\oplus15,15)=\text{gcd}(34,15)=1$$$
  • $$$k=4$$$, $$$\text{gcd}(kx \oplus x,x)=\text{gcd}(60\oplus15,15)=\text{gcd}(51,15)=3$$$

So the answer to interval $$$[1,4]$$$ is $$$2$$$.