Zadanie

Isté veci máme radi

Počet bodov: 55

Hodobox má isté veci rád. Rád delí svoj čas na rekreačný a spánkový. Rád sčítava svoje body za úlohy na SPOJi. Rád chodí do nového roku, keď už nemusí písať dátumy do zošitov. Rád zneužíva svoju moc nad riešiteľmi ZENITu. Má rád číslo \(47\).

Dávid chce spraviť Hodoboxovi radosť, a umožniť mu robiť tieto aktivity naraz - delenie, sčítavanie, 2023kovanie, 47kovanie, umocňovanie.

Rozhodol sa Hodoboxovi darovať program, ktorý bude robiť všetky tieto veci.

A aby z toho nevynechal aj riešiteľov ZENITu, nechá tento darček pripraviť vás.

Úloha

Postup:

Zoberieme rok \(2023\).

Umocníme ho na nejakú mocninu \(X\).

Nájdeme všetky celočíselné delitele tohto čísla.

Sčítame ich.

Nájdeme zvyšok tohto súčtu po delení číslom \(47\).

Tento zvyšok vypíšeme na výstup.

Program čo toto zvládne submitneme.

Získame body v ZENITe.

Vstup a Výstup

V prvom riadku vstupu je číslo \(T\), určujúce koľko krát si Hodobox chce spraviť radosť.

V každom z ďalších \(T\) riadkov je jedno celé číslo \(X\) - mocninu, ktorú Hodobox túži použiť.

Pre každé \(X\) vypíšte výsledok ako bol popísaný v úlohe, teda súčet všetkých deliteľov \(2023^X\), modulo \(47\).

V prvej sade \(T = 5\) a \(1 \leq X \leq 5\).

V druhej sade \(T = 50\) a \(1 \leq X \leq 50\).

V tretej sade \(T = 5\) a \(1 \leq X \leq 10000\).

V štvrtej sade \(T = 1\) a \(1 \leq X \leq 50000\).

V piatej sade \(T = 100\) a \(1 \leq X \leq 10^9\).

Príklady

Input:

3
1
2
3

Output:

12
3
3

\(2023^2 = 4092529\). Jeho deliteľe sú \(1, 7, 17, 49, 119, 289, 833, 2023, 4913, 14161, 34391, 83521, 240737, 584647, 4092529\). Ich súčet je \(5058237\). \(5058237 = 107622 \cdot 47 + 3\).

Input:

3
10
20
30

Output:

32
31
12