Hôm nay, Blue được học về ước và bội. Ước của một số nguyên không âm ~a~ là ~x~ khi ~a~ chia hết cho ~x~. Bội của một số nguyên dương ~a~ là ~x~ khi ~x~ chia hết cho ~a~. Mở rộng hơn chúng ta có ước chung lớn nhất của hai số nguyên không âm ~a~ và ~b~, được ký hiệu là ~GCD(a, b)~, là số nguyên không âm lớn nhất vừa là ước của ~a~ vừa là ước của ~b~. Còn bội chung nhỏ nhất của hai số nguyên không âm ~a~ và ~b~ sẽ được ký hiệu là ~LCM(a, b)~ và là số nguyên không âm nhỏ nhất vừa chia hết cho ~a~ và chia hết cho ~b~. Sau khi liệt kê danh sách ước của một vài số, Blue nhận ra có những số mang một tính chất rất đặc biệt, đó là tổng ước chung lớn nhất và bội chung nhỏ nhất của số ước chẵn và số ước lẻ của số đó là số lẻ. Cụ thể hơn, xét số nguyên ~x~ có ~a~ ước chẵn và ~b~ ước lẻ. ~x~ là số nguyên đặc biệt khi ~GCD(a, b) + LCM(a, b)~ là số lẻ. Tuy nhiên, vì sẽ có nhiều số mà số ước của nó rất lớn, nên Blue chỉ quan tâm đến những số đặc biệt có số lượng ước bé hơn hoặc bằng ~K~. Blue muốn nhờ bạn, một lập trình viên tài năng, trả lời các câu hỏi của Blue rằng trong các số nguyên từ ~l~ tới ~r~ sẽ có bao nhiêu số đặc biệt mà có số ước bé hơn hoặc bằng ~K~.

INPUT

• Dòng đầu tiên là số nguyên dương ~K~ (~K ≤ 1000000~)
• Dòng thứ hai gồm số nguyên dương ~T~ là số câu hỏi của Blue
• ~T~ dòng tiếp theo, mỗi dòng sẽ gồm 2 số nguyên dương ~l, r~ (~l ≤ r~)

OUTPUT

• Gồm ~T~ dòng, dòng thứ ~i~ là câu trả lời cho câu hỏi thứ ~i~

Ví dụ

Input 1

4
2
3 4
5 6

Output 1

1
0

Input 2

2
2
3 4
5 6

Output 2

0
0

Giải thích:

• ~3~ có ~0~ ước chẵn và ~2~ ước lẻ {~1~, ~3~} ~⇒ GCD(0, 2) + LCM(0, 2) = 2 + 0 = 2~ là số chẵn
• ~4~ có ~2~ ước chẵn {~2~, ~4~} và ~1~ ước lẻ {~1~} ~⇒ GCD(2, 1) + LCM (2, 1) = 1 + 2 = 3~ là số lẻ
• ~5~ có ~0~ ước chẵn và ~2~ ước lẻ {~1~, ~5~} ~⇒ GCD(0, 2) + LCM(0, 2) = 2 + 0 = 2~ là số chẵn
• ~6~ có ~2~ ước chẵn {~2~, ~6~} và ~2~ ước lẻ {~1~, ~3~} ~⇒ GCD(2, 2) + LCM(2, 2) = 2 + 2 = 4~ là số chẵn

Subtask 1 : 40% số test thỏa mãn ~T ≤ 100, 1 ≤ l ≤ r ≤ 100~

Subtask 2 : 30% số test thỏa mãn ~T ≤ 100000, 1 ≤ l ≤ r ≤ 1000000~

Subtask 3 : 30% số test thỏa mãn ~T ≤ 100000, 1 ≤ l ≤ r ≤ 1000000000000~