오름차순

숫자로 구성된 문자열이 주어진다. 문자 사이에 공백을 적절히 추가해서 $1$개 이상의 부분문자열로 나누려고 한다.

단, 아래 조건을 만족해야 한다.

• 각 부분문자열이 나타내는 수는 오름차순이어야 한다. 단, 한 번의 예외를 둘 수 있다.
• 가능한 많은 부분문자열을 만들어야 한다.

각 부분문자열이 나타내는 수가 오름차순이라는 것은 모든 인접한 두 수에 대해 오른쪽의 수가 왼쪽의 수보다 크거나 같음을 의미한다. 여기에서 한 번의 예외를 둘 수 있다는 것은 최대 하나의 경우에 대해 왼쪽의 수가 오른쪽의 수보다 클 수 있음을 의미한다.

예를 들어, 33133의 경우, 부분문자열이 나타내는 수가 오름차순이 되도록 공백을 추가하여 가장 많은 부분문자열을 만들 수 있는 경우는 3, 3, 133, 또는 3, 31, 33이다. 그러나 첫 번째 조건에서 한 번의 예외를 둘 수 있으므로, 이를 고려하면 3, 3, 1, 3, 3이 된다.

부분문자열이 0으로 시작할 수 있음에 유의하라. 예를 들어, 103201을 1, 03, 201로 나눌 수 있고, 이 부분문자열들이 나타내는 수는 각각 1, 3, 201이다.

주어진 문자열에 대해 조건을 만족하며 부분문자열로 나눌 때, 부분문자열의 개수를 구하는 프로그램을 작성하라.

입력 형식

첫 줄에 문자열의 수를 나타내는 정수 $T$가 주어진다. ($T \geq 1$)

이어지는 $2T$ 개의 줄에는 차례로 각 문자열에 대한 정보들이 주어진다.

$2T$ 개의 줄의 $2i-1$ 번째 줄에 $i$ 번째 문자열의 길이를 나타내는 정수 $N_i$가 주어진다. ($1 \leq N_i \leq 3\,000$)

$2T$ 개의 줄의 $2i$ 번째 줄에 $i$ 번째 문자열이 주어진다. 이 문자열은 0부터 9까지 숫자로 이루어져 있다.

입력으로 주어지는 문자열의 길이 합, 즉, $N_1 + N_2 + \cdots + N_T$는 $3\,000$을 넘지 않는다.

출력 형식

$T$ 개의 줄에 걸쳐 답을 출력한다. $i$ 번째 줄에 $i$ 번째 문자열을 조건을 만족하며 부분문자열로 나눌 때, 부분문자열의 개수를 출력한다.

예제

2
5
33133
6
103201

5
4

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설