Se dă n un număr natural și n perechi de numere (a, b).

Cerința

Să se determine:

• Câte numere din intervalul închis determinat de a și b au număr impar de divizori pozitivi.
• Câte numere cu exact trei divizori pozitivi se găsesc în intervalul închis determinat de a și b.

Date de intrare

Fișierul de intrare cate.in conține pe prima linie două numere naturale C și n, separate printr-un spațiu. C reprezintă cerința care trebuie rezolvată (1 sau 2), iar n reprezintă numărul de perechi. Pe următoarele n linii se găsesc cele n perechi de numere naturale, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire cate.out va conține n linii. Pe linia i trebuie să se găsească răspunsul la întrebarea corespunzătoare de pe linia i+1 a fișierului de intrare.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ a, b ≤ 1.000.000
• Pentru 42 de puncte, C = 1
• Pentru 58 de puncte, C = 2

Exemplul 1:

cate.in

1 3
1 10
30 10
100 500

cate.out

3
2
13

Explicație

În intervalul [1, 10] sunt 3 numere cu număr impar de divizori: 1, 4, 9.
În intervalul [10, 30] sunt 2 numere cu număr impar de divizori: 16, 25.
În intervalul [100, 500] sunt 13 numere cu număr impar de divizori.

Exemplul 2:

cate.in

2 3
1 10
30 10
100 500

cate.out

2
1
4

Explicație

În intervalul [1, 10] sunt 2 numere cu exact 3 divizori: 4, 9.
În intervalul [10, 30] este doar un număr cu exact 3 divizori: 25.
În intervalul [100, 500] sunt 4 numere cu exact 3 divizori.