길이 $N$의 문자열 $S = S_1 S_2 \cdots S_N$이 주어진다. 각 $S_i$는 $\texttt{C}$ 또는 $\texttt{P}$이다.

$S$의 cyclic shift $R$를 선택한 뒤, $R$에서 $0$개 이상의 문자를 삭제하여 새로운 문자열 $U$를 만든다. 이때 삭제되지 않은 문자들의 상대적인 순서는 유지된다.

이때 문자열 $U$의 길이 $3$인 연속된 부분문자열 중 $\texttt{CPP}$와 일치하는 것이 존재하지 않도록 해야 한다.

이 조건을 만족하도록 $U$를 만들 때, 가능한 $U$의 길이의 최댓값을 구하여라.

입력 형식

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10^6$)

각 테스트 케이스는 두 줄로 이루어져 있으며, 첫째 줄에 정수 $N$이 주어진다. ($1 \le N \le 10^6$)

둘째 줄에 길이 $N$의 문자열 $S$가 주어진다. $S$는 알파벳 대문자 $\texttt{C}$ 또는 $\texttt{P}$로만 이루어진 문자열이다.

모든 테스트 케이스에 대해 $N$의 합이 $10^6$을 초과하지 않음이 보장된다.

출력 형식

각 테스트 케이스마다 조건을 만족하는 $U$의 길이의 최댓값을 한 줄에 하나씩 출력하여라.

예제

예제 1

입력

2
5
CPPCP
6
CPCPCP

출력

5
6

노트

문자열 $R = R_1 R_2 \cdots R_N$이 $S$의 cyclic shift라는 것은, 어떤 정수 $k$ ($1 \le k \le N$)가 존재하여 $R_i = S_{((k + i - 2) \bmod N) + 1}$ 를 모든 $1 \le i \le N$에 대해 만족하는 것을 의미한다.

문자열 $U$의 연속된 부분문자열은 어떤 $1 \le l \le r \le |U|$에 대해 $$U_l U_{l+1} \cdots U_r$$ 형태의 문자열을 의미한다.