题目描述

你的朋友 John 刚度假回来，他想和你分享一个关于字符串的新性质。

John 学到，一个由大写英文字母组成的长度为 $L$ 的字符串 $C$ 是 严格递增 的，如果对于每一对下标 $i$ 和 $j$，满足 $1 \le i < j \le L$（下标从 $1$ 开始），位置 $i$ 上的字符小于位置 $j$ 上的字符。

例如，字符串 ABC 和 ADF 是严格递增的，而字符串 ACC 和 FDA 则不是。

现在他教了你这个有趣的新性质，John 决定挑战你：给定一个长度为 $N$ 的字符串 $S$，你需要对每个位置 $1 \le i \le N$，求出以位置 $i$ 结尾的最长严格递增子串的长度。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例由两行组成。

第一行包含一个整数 $N$，表示字符串的长度。

第二行包含一个长度为 $N$ 的字符串 $S$，由大写英文字母组成。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y1 y2 ... yn，其中 $x$ 是测试用例编号（从 $1$ 开始），$y_i$ 是以位置 $i$ 结尾的最长严格递增子串的长度。

2
4
ABBC
6
ABACDA

Case #1: 1 2 1 2
Case #2: 1 2 1 2 3 1

提示

在样例 #1 中，以位置 $1$ 结尾的最长严格递增子串是 A。以位置 $2$、$3$、$4$ 结尾的最长严格递增子串分别为 AB、B 和 BC。

在样例 #2 中，每个位置的最长严格递增子串分别为 A、AB、A、AC、ACD 和 A。

限制条件

$1 \le T \le 100$。

测试集 1

$1 \le N \le 100$。

测试集 2

$1 \le N \le 2 \times 10^5$。

翻译由 DeepSeek V4 Pro 完成