Байтоша недавно научилась умножать, и ей очень понравилось это занятие.

Она придумала следующую игру с умножением цифр. Она начинает с того, что записывает на доске некоторое положительное целое число $x$. Затем она перемножает цифры этого числа (в десятичной системе счисления) и заменяет старое значение $x$ полученным результатом. Этот шаг повторяется до тех пор, пока $x$ не станет однозначным числом. Отдельная игра на умножение заканчивается на этом числе. Можно доказать, что игра всегда заканчивается, независимо от начального значения $x$.

Например, игра может начаться с $x = 57$. После первого шага Байтоша переходит к числу $5 \cdot 7 = 35$. На следующем шаге она переходит к числу $3 \cdot 5 = 15$, а на последнем шаге — к числу $1 \cdot 5 = 5$. Это число является однозначным, поэтому игра заканчивается на цифре 5.

Если бы начальным числом было $x = 255$, то за один шаг Байтоша получила бы число $2 \cdot 5 \cdot 5 = 50$, а уже на втором шаге — число $5 \cdot 0 = 0$. Игра закончилась бы на цифре 0.

Вернувшись из детского сада, Байтоша начинает игры на умножение, всегда начиная с последовательных значений: Первую игру она начинает с $x = 1$ и сразу заканчивает на цифре 1. Вторую игру она начинает с $x = 2$ и сразу заканчивает на цифре 2. ... Десятую игру она начинает с $x = 10$ и заканчивает на цифре 0. Одиннадцатую игру она начинает с $x = 11$ и заканчивает на цифре 1. ... Пятьдесят шестую игру она начинает с $x = 56$ и заканчивает на цифре 0. Пятьдесят седьмую игру она начинает с $x = 57$ и заканчивает на цифре 5. * ...

В течение $t$ дней Байтоша после возвращения из детского сада начинала такую последовательность игр на умножение цифр, и каждый день игры ей в конце концов надоедали. А именно, в $i$-й день Байтоша провела $n_i$ игр на умножение, причем последняя из них начиналась со значения $x = n_i$.

Для каждого дня, имея данные $n_i$, определите для каждой цифры от 0 до 9, сколько игр на умножение цифр закончилось на этой цифре.

Входные данные

Первая строка содержит целое число $t$ ($1 \le t \le 1000$), обозначающее количество дней, в которые Байтоша играла в умножение цифр.

Вторая строка содержит последовательность из $t$ целых чисел $n_1, n_2, \dots, n_t$ ($1 \le n_i \le 10^{18}$), обозначающих, сколько игр на умножение Байтоша провела в соответствующие дни.

Выходные данные

Выведите $t$ строк, каждая из которых должна содержать 10 целых чисел, обозначающих количество игр на умножение в соответствующий день, которые закончились на цифрах 0, 1, ..., 9 соответственно.

Примеры

Пример 1

5
10 56 57 123 1

Выходные данные 1

1 1 1 1 1 1 1 1 1 1
11 2 7 3 6 5 8 2 9 3
11 2 7 3 6 6 8 2 9 3
36 3 11 4 12 8 16 4 24 5
0 1 0 0 0 0 0 0 0 0