Mihai decide că e vremea să își construiască propria casă și are nevoie de un arhitect priceput. Auzind el despre arhitectul Gigel, intenționează să îl contacteze. Construirea unei case fiind o chestiune serioasă, Mihai vrea să testeze competențele lui Gigel și îi pregătește mai multe întrebări de următoarele două tipuri:

• Tipul 1: O cameră cu suprafața N trebuie împărțită în zone cu aceeași suprafață, număr natural. În câte moduri se poate face această împărțire?
• Tipul 2: Două camere cu suprafețele a și b pot fi vecine doar dacă a și b au un divizor comun mai mare decât 1. Câte perechi numere naturale din intervalul [1, N] pot fi suprafețele unor camere vecine?

Fiindcă are foarte mulți clienți, Gigel vă cere din nou ajutorul.

Cerința

Scrieți un program care citește Q astfel de întrebări și care afișează răspunsurile la fiecare dintre ele.

Date de intrare

Fișierul de intrare divq.in va conține:
• Pe prima linie numărul Q, reprezentând numărul de întrebări.
• Pe următoarele Q linii câte două numere, T și N, unde T reprezintă tipul întrebării (1 sau 2) și N are semnificația din enunț.

Date de ieșire

Fișierul de ieșire divq.out va conține răspunsurile la fiecare dintre cele Q întrebări ale lui Mihai, fiecare rezultat fiind afișat pe câte o linie.

Restricții și precizări

• 1 ≤ T ≤ 2
• 1 ≤ N ≤ 1.500.000, N număr întreg
• 1 ≤ Q ≤ 1.000.000
• pentru întrebările de tipul 1 se ia în considerare și camera nemodificată
• pentru 23 de puncte avem numai întrebări de tip 1, dintre care 5 puncte sunt pentru N ≤ 100.000
• pentru 35 de puncte avem numai întrebări de tip 2, dintre care 6 puncte sunt pentru Q ≤ 10, N ≤ 1000 și 15 sunt pentru Q ≤ 100
• pentru încă 7 puncte, 1 ≤ T ≤ 2 , Q ≤ 100

Exemplu:

divq.in

5
1 16
2 6
1 1
2 3
1 7

divq.out

5
4
1
0
2

Explicație

• Prima întrebare este de tipul 1. Camera cu suprafața 16 poate fi împărțită în camere cu suprafețele 1, 2, 4, 8, 16.
• A doua întrebare este de tipul 2. Sunt 4 perechi de numere cuprinse între 1 și 6 care au divizor comun mai mare decât 1, și anume: (2, 4), (2, 6), (3, 6), (4, 6)
• A treia întrebare este de tipul 1. Camera cu suprafața 1 se “împarte” într-un singur mod.
• A patra întrebare este de tipul 2. Nu există perechi de numere cuprinse între 1 și 3 care au divizor comun mai mare decât 1.
• A cincea întrebare este de tipul 1. Camera cu suprafața 7 se împarte în camere cu suprafețele 1 și 7.