증가하는 부분 문자열

친구 John이 방금 휴가에서 돌아왔고, 문자열에 관해 새로 알게 된 성질을 여러분에게 알려 주고 싶어 한다.

John은 대문자 영어 문자로 이루어진 길이 $L$의 문자열 $C$에서, $1 \le i \lt j \le L$를 만족하는 모든 인덱스 쌍 $i$와 $j$에 대해($1$ 기준), 위치 $i$의 문자가 위치 $j$의 문자보다 작으면 그 문자열이 엄격히 증가한다는 것을 알게 되었다.

예를 들어, 문자열 ABC와 ADF는 엄격히 증가하지만, 문자열 ACC와 FDA는 그렇지 않다.

이 흥미로운 새 성질을 알려 준 John은 이제 여러분에게 도전 과제를 내기로 했다. 길이 $\mathbf{N}$의 문자열 $\mathbf{S}$가 주어질 때, 모든 위치 $1 \le i \le \mathbf{N}$에 대해 위치 $i$에서 끝나는 가장 긴 엄격히 증가하는 부분 문자열의 길이를 구해야 한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 100$.

테스트 세트 2

시간 제한: 40초. $1 \le \mathbf{N} \le 2 \times 10^5$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다.

첫 번째 줄에는 문자열의 길이를 나타내는 정수 $\mathbf{N}$이 주어진다.

두 번째 줄에는 대문자 영어 문자로 이루어진 길이 $\mathbf{N}$의 문자열 $\mathbf{S}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y_1$ $y_2$ ... $y_n$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y_i$는 위치 $i$에서 끝나는 가장 긴 엄격히 증가하는 부분 문자열의 길이이다.

예제 케이스 #1에서 위치 $1$에서 끝나는 가장 긴 엄격히 증가하는 부분 문자열은 A이다. 위치 $2$, $3$, $4$에서 끝나는 가장 긴 엄격히 증가하는 부분 문자열은 각각 AB, B, BC이다.

예제 케이스 #2에서 각 위치에 대한 가장 긴 엄격히 증가하는 부분 문자열은 A, AB, A, AC, ACD, A이다.