5. Poradie trpaslíkov

Táto úloha sa dá nahradiť riešením sady arrays_cpp na Liahni (betaliahen.ksp.sk) . Ak chceš, aby ti namiesto bodov za riešenie tejto úlohy boli započítané body získané riešením spomínanej sady, na stránke odovdzaj pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Mišovi “Žabovi” Anderlemu na

Všetci určite poznáte rozprávku o Snehulienke a siedmich trpaslíkoch. Snehulienka sa stratila v lese, našla domček v ktorom bývali trpaslíci, bol tam strašný neporiadok, a ona začala upratovať… Viete prečo nemali trpaslíci doma upratané? Nie, nebolo to preto, že by boli leniví… Trpaslíci toho majú len veľa na práci. Preto majú presne rozdelené, kto má čo spraviť, podľa poradia v ktorom sa v daný deň zobudili. Prvý chystá raňajky, druhý pripravuje stôl, tretí varí čaj, štvrtý upratuje… Aby sa v činnostiach vystriedali, a tiež, aby nemusel Spachtoš vždy vstávať ako prvý, každý deň vstávajú v inom poradí.

Aby trpaslíci vedeli zistiť, že sa už vystriedali všetky poradia, používajú nasledovný systém:

• Každý z trpaslíkov má svoju obľúbenú cifru od \(0\) do \(9\).
• Keď trpaslík ráno vstane, napíše svoju obľúbenú cifru na tabuľu, hneď za poslednú, ktorá tam bola. Takto vznikne každý deň na tabuli jedno číslo.
• Trpaslíci si počítajú súčet čísel, ktoré sa objavujú na tabuli – predtým, ako idú spať, pripočítajú číslo z tabule k súčtu.
• Keď je súčet dostatočne veľký, vystriedali sa všetky poradia a môžu sa začať striedať (a sčítavať) odznova.

Systém je dokonalý, no trpaslíci majú jeden problém. Nevedia, aký súčet má byť na tabuli po tom, čo sa vystriedali všetky poradia. Niekedy si tak nevšimnú, že sa už vystriedali a nasledujúce ráno nevstane nikto. Práve v takýto deň prišla Snehulienka a tá sa ako silná žena a nádejná programátorka rozhodla vyriešiť tento problém raz a navždy.

Úloha

Pre jednu domácnosť trpaslíkov dostanete jedno číslo \(c_i\), ktoré vzniklo na tabuli v prvý deň. Zistite, aký bude súčet čísel z tabule, keď sa vystriedajú všetky poradia trpaslíkov. Stručne povedané, zistite súčet všetkých permutácií cifier čísla \(c_i\).

Úlohu vyriešte pre \(n\) rôznych domácností trpaslíkov.

Formát vstupu

Na prvom riadku je číslo \(n\) (\(1 \leq n \leq 10^5\)). Nasleduje \(n\) riadkov, v každom z nich je jedno číslo \(c_i\) (\(0 \leq c_i \leq 10^{12}\)). Žiadne číslo iné ako 0 nezačína nulou.

Formát výstupu

Vypíšte \(n\) riadkov, na \(i\)-tom riadku bude súčet permutácií cifier \(i\)-teho čísla zo vstupu. Každý súčet sa zmestí do 64 bitovej premennej (typu Int64 v Pascale, long long v C++).

Príklad

Input:

5
2
47
33
750
4247

Output:

2
121
66
2664
113322

Trpaslík s cifrou \(2\) býva sám, preto musí vždy vstať prvý. Pre trpaslíkov s ciframi \(4\) a \(7\) existujú dve poradia, ako môžu vstať (\(47\) a \(74\)). Trpaslíci v tretej domácnosti majú rovnaké obľúbené cifry, ale aj tak ich rozlišujeme a preto majú tiež dve možnosti.