POLSKI SPOJ

Jasiu przeglądając stare notatki swojego dziadka Bajtomira zauważył pewien skomplikowany dla niego wzór: 

gdzie n ≥ 2 i należy do liczb całkowitych, a D(k) oznacza liczbę całkowitych dodatnich dzielników k.

Na przykład dla n = 72 nasz wzór ma postać:

D(1)+D(2)+D(3)+D(4)+D(6)+D(8)+D(9)+D(12)+D(18)+D(24)+D(36)+D(72)=

 1+2+2+3+4+4+3+6+6+8+9+12=60

Jasiu mając daną liczbę podaną w postaci iloczynu różnych potęg liczb pierwszych chce poznać tę sumę, a ty musisz mu w tym pomóc :-)

Wejście

W pierwszym wierszu jedna liczba q określająca ilość zapytań (q < 10⁵).

Specyfikacja każdego zapytania:

najpierw jedna liczba k określająca ilość liczb w postaci par p^s, gdzie p to liczba pierwsza a s  jej wykładnik, następnie w kolejnym wierszu  k par liczb p i s (k < 10, p < 10⁵, s < 11). Można założyć, że podstawy są prami różne.

Wyjście

Do każdego zapytania należy podać w oddzielnej linii szukaną sumę.

Przykład

Wejście:
1
2
2 3 3 2
Wyjście:
60