F. Билеты
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последние $$$n$$$ дней Монокарп добирался до университета на маршрутке. Во время $$$i$$$-й поездки ему выдавался билет с номером $$$t_i$$$.

Номера билетов представляют собой шестизначные целые числа, которые могут содержать лидирующие нули. Например, $$$123456$$$, $$$000000$$$, $$$099999$$$, $$$999999$$$ — это корректные номера билетов, а $$$1234567$$$, $$$12345$$$, $$$9$$$ — нет. Каждый день нумерация билетов начинается с нуля. Первый пассажир в каждый из дней получает билет с номером $$$000000$$$, второй пассажир — с номером $$$000001$$$, третий пассажир — с номером $$$000002$$$ и так далее. Считайте, что количество пассажиров за день не превосходит $$$10^6$$$.

Неудачливость билета равна модулю разности между суммой первых трёх цифр билета и суммой последних трёх цифр билета. Например, неудачливость билета с номером $$$345123$$$ равна $$$|(3 + 4 + 5) - (1 + 2 + 3)| = 6$$$, а неудачливость билета с номером $$$238526$$$ равна $$$|(2 + 3 + 8) - (5 + 2 + 6)| = 0$$$.

Один пассажир удачливее второго, если неудачливость билета первого пассажира строго меньше, чем неудачливость билета второго.

Для каждого из $$$n$$$ дней по номеру билета Монокарпа $$$t_i$$$ определите количество пассажиров в соответствующий день, которые получили билетики до Монокарпа и являются удачливее Монокарпа.

Рассмотрите примеры для более четкого понимания условия.

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

В первой строке следует целое число $$$n$$$ $$$(1 \le n \le 2\cdot10^{5})$$$ — количество дней поездок на маршрутке.

В следующих $$$n$$$ строках следует по одному шестизначному целому числу $$$t_i$$$ ($$$0 \le t_i \lt 10^6$$$, $$$t_i$$$ может содержать лидирующие нули) — номера билетов, которые получил Монокарп в соответствующий день.

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

Выведите в $$$n$$$ строк по одному целому числу — количество пассажиров в соответствующий день, которые получили билетики до Монокарпа и являются удачливее Монокарпа.

Пример
Входные данные
5
001000
000000
999000
453234
654331
Выходные данные
1
0
998999
121496
470362
Примечание

В первый день лишь один пассажир, получивший билет до Монокарпа, был удачливее чем он. Этот пассажир получил билет с номером $$$000000$$$.

Во второй день Монокарп получил билет самым первым, поэтому до него не было ни одного пассажира.

В третий день все пассажиры кроме одного, получившие билеты до Монокарпа, были удачливее, чем он. Единственный пассажир, неудачливость которого равна неудачливости Монокарпа, получил билет с номером $$$000999$$$.