题目描述

给定一个长度为 $n$，仅由数字组成的字符串 $s$。

$s$ 的子串指其一段连续的字符。子串 $s_{l \dots r}$ 是坏子串，当且仅当它包含 $2025$ 作为子序列，并且不包含 $2026$ 作为子序列。其余情况的子串都是好子串。 例如：$2025$、$72707275$、$20625$ 是坏子串；而 $20256$、$2026$、$777$、$1290723576$ 是好子串。

对每个下标 $i$（$1 \le i \le n$），求出包含位置 $i$ 的好子串数量。也就是，对每个 $i$，求满足 $1 \le l \le i \le r \le n$，且子串 $s_{l\dots r}$ 是好子串的 $(l,r)$ 对数。

输入格式

第一行一个整数 $t$（$1 \le t \le 10^4$），代表测试用例数量。

每组测试用例第一行一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）。

第二行给出长度为 $n$ 的数字字符串 $s$。

额外约束：所有测试用例的 $n$ 之和不超过 $3\cdot 10^5$。

输出格式

对每组测试用例，输出 $n$ 个整数。第 $i$ 个整数代表包含下标 $i$ 的好子串数量。

2
6
202516
5
20265

4 8 10 10 9 6 
5 8 9 8 5 

原题链接

原题链接