CF2276E Good Substrings

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.

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 $ .

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