E. Good Substrings
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ of length $$$n$$$, consisting only of digits.

A substring of $$$s$$$ is a contiguous subsequence of its characters. A substring $$$s_{l \dots r}$$$ is bad if it contains the string $$$2025$$$ as a subsequence and doesn't contain the string $$$2026$$$ as a subsequence. Otherwise, the substring is good. For example, the strings $$$2025$$$, $$$72707275$$$, $$$20625$$$ are bad, but the strings $$$20256$$$, $$$2026$$$, $$$777$$$, $$$1290723576$$$ are good.

For each index $$$i$$$ from $$$1$$$ to $$$n$$$, calculate the number of good substrings that contain it. In other words, for each index $$$i$$$ from $$$1$$$ to $$$n$$$, calculate the number of pairs of integers $$$l, r$$$ such that $$$1 \le l \le i \le r \le n$$$ and the substring $$$s_{l \dots r}$$$ is good.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).

The second line contains a string $$$s$$$ of length $$$n$$$, consisting of digits.

Additional constraint on the input: the sum of $$$n$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print $$$n$$$ integers. The $$$i$$$-th integer should be equal to the number of good substrings that contain index $$$i$$$.

Example
Input
2
6
202516
5
20265
Output
4 8 10 10 9 6 
5 8 9 8 5