Tényezők

Az aritmetika alaptétele szerint minden 1-nél nagyobb egész szám egyértelműen felírható egy vagy több prímszám szorzataként. Bár a felírás egyértelmű, a prímtényezőknek számos elrendezése létezhet. Például:

            10 = 2 * 5                20 = 2 * 2 * 5
               = 5 * 2                   = 2 * 5 * 2
                                         = 5 * 2 * 2

Jelölje f(k) a k szám prímtényezői különböző elrendezéseinek a számát! Ekkor tehát f(10) = 2 és f(20) = 3.

Adott pozitív n szám esetén mindig létezik legalább egy olyan k szám, amelyre f(k) = n. A legkisebb ilyen k-t keressük.

A bemenet specifikációja

A bemenet legfeljebb 1000 tesztesetből áll, mindegyik külön sorban. Minden teszteset egy n < 2⁶³ pozitív egész szám.

A kimenet specifikációja

Minden tesztesetre a kimenetre kell írni az n számot, valamint (egy szóköz után) a legkisebb olyan k > 1 értéket, amelyre f(k) = n. A bemeneten szereplő számok úgy lesznek megválasztva, hogy k < 2⁶³.

Példa bemenet

1. 1
2. 2
3. 3
4. 105

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 1 2
2. 2 6
3. 3 12
4. 105 720

letöltés szöveges állományként