Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_05_10 - Dzielniki dzielników

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

 

dzielniki

gdzie ≥ 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 < 105).

Specyfikacja każdego zapytania:

najpierw jedna liczba określająca ilość liczb w postaci par ps, gdzie p to liczba pierwsza a s  jej wykładnik, następnie w kolejnym wierszu  k par liczb p i (k < 10, < 105, 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

Dodane przez:Marcin Kasprowicz
Data dodania:2016-03-02
Limit czasu wykonania programu:0.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.