Дана строка $$$s$$$ длины $$$n$$$, состоящая только из цифр.
Подстрока строки $$$s$$$ — это непрерывная подпоследовательность её символов. Подстрока $$$s_{l \dots r}$$$ называется плохой, если она содержит строку $$$2025$$$ как подпоследовательность и не содержит строку $$$2026$$$ как подпоследовательность. В противном случае подстрока называется хорошей. Например, строки $$$2025$$$, $$$72707275$$$, $$$20625$$$ являются плохими, а строки $$$20256$$$, $$$2026$$$, $$$777$$$, $$$1290723576$$$ — хорошими.
Для каждого индекса $$$i$$$ от $$$1$$$ до $$$n$$$ вычислите количество хороших подстрок, которые содержат его. Иными словами, для каждого индекса $$$i$$$ от $$$1$$$ до $$$n$$$ вычислите количество пар целых чисел $$$l, r$$$ таких, что $$$1 \le l \le i \le r \le n$$$ и подстрока $$$s_{l \dots r}$$$ является хорошей.
В первой строке содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).
Во второй строке содержится строка $$$s$$$ длины $$$n$$$, состоящая из цифр.
Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел; $$$i$$$-е число должно быть равно количеству хороших подстрок, которые содержат индекс $$$i$$$.
26202516520265
4 8 10 10 9 65 8 9 8 5
