33824번 - Mnożenie cyfr 다국어

문제

Bajtosia niedawno nauczyła się mnożyć i bardzo jej się to mnożenie spodobało.

Wymyśliła następującą zabawę w mnożenie cyfr. Zaczyna, pisząc na tablicy pewną dodatnią liczbę całkowitą $x$. Następnie mnoży przez siebie cyfry tej liczby (w systemie dziesiętnym), a otrzymanym wynikiem zastępuje starą wartość $x$. Ten krok powtarza w kółko, aż $x$ ustabilizuje się jako liczba jednocyfrowa. Pojedyncza zabawa w mnożenie kończy się wtedy tą liczbą. Da się udowodnić, że zabawa zawsze się zakończy, niezależnie od początkowej wartości $x$.

Przykładowo, zabawa może zacząć się z $x = 57$. Po pierwszym kroku Bajtosia przechodzi do liczby 5ドル \cdot 7 = 35$. W następnym przechodzi do liczby 3ドル \cdot 5 = 15,ドル a w ostatnim kroku przechodzi do liczby 1ドル \cdot 5 = 5$. Liczba ta jest jednocyfrowa, więc zabawa się kończy na cyfrze 5ドル$.

Natomiast gdyby początkową liczbą było $x = 255,ドル to w jednym kroku Bajtosia otrzymałaby liczbę 2ドル \cdot 5 \cdot 5 = 50,ドル a już w drugim liczbę 5ドル \cdot 0 = 0$. Zabawa skończyłaby się na cyfrze 0ドル$.

Po powrocie z przedszkola Bajtosia rozpoczyna zabawy w mnożenie i robi to zawsze zaczynając z kolejnych wartości:

• Pierwszą zabawę zaczyna z $x = 1$ i od razu kończy na cyfrze 1ドル$.
• Drugą zabawę zaczyna z $x = 2$ i od razu kończy na cyfrze 2ドル$.
• $\dots$
• Dziesiątą zabawę zaczyna z $x = 10$ i kończy na cyfrze 0ドル$.
• Jedenastą zabawę zaczyna z $x = 11$ i kończy na cyfrze 1ドル$.
• $\dots$
• Pięćdziesiątą szóstą zabawę zaczyna z $x = 56$ i kończy na cyfrze 0ドル$.
• Pięćdziesiątą siódmą zabawę zaczyna z $x = 57$ i kończy na cyfrze 5ドル$.
• $\dots$

Przez kolejne $t$ dni Bajtosia po powrocie z przedszkola rozpoczynała taki ciąg zabaw w mnożenie cyfr i każdego dnia zabawy się jej w końcu nudziły, dokładniej $i$-tego dnia Bajtosia wykonała $n_i$ zabaw w mnożenie – ostatnią z nich zaczynając z wartości $x = n_i$.

Dla każdego dnia, mając dane $n_i,ドル wyznacz dla każdej cyfry od 0ドル$ do 9ドル,ドル ile zabaw w mnożenie cyfr skończyło się na tej cyfrze.

입력

Pierwszy wiersz zawiera liczbę całkowitą $t$ (1ドル ≤ t ≤ 1000$), oznaczającą liczbę dni, w których Bajtosia bawiła się w mnożenia cyfr.

Drugi wiersz zawiera ciąg $t$ liczb całkowitych $n_1, n_2, \dots , n_t$ (1ドル ≤ n_i ≤ 10^{18}$), oznaczających ile zabaw w mnożenie Bajtosia wykonała w kolejne dni.

출력

Na wyjście należy wypisać $t$ wierszy, każdy z nich powinien zawierać 10ドル$ liczb całkowitych, oznaczających kolejno ile zabaw w mnożenie odpowiedniego dnia zakończyło się na cyfrach 0,ドル 1, \dots , 9$.

제한

힌트