题目描述

You are given a word $S$ written in an unfamiliar language. In this language, a syllable is known to be one of the following:

• A single uppercase English letter
• A single lowercase English letter
• An uppercase English letter followed by a lowercase English letter

For example, "Ab", "A", and "c" can each form a syllable, but "IC", "pC", and "Jag" cannot.

When dividing a word $S$ into several contiguous substrings that are syllables, determine the minimum and maximum possible number of distinct syllables among them.

输入格式

The input consists of multiple test cases.

The first line contains an integer $T$ ($1 \leq T \leq 10000$), representing the number of test cases.

$T$ test cases follow. Each test case is given in the following format.

For each test case, the only line contains a string $S$ ($1 \leq |S| \leq 10^6$), consisting of uppercase and lowercase English letters.

Additionally, the sum of the lengths of $S$ over all test cases does not exceed $10^6$.

输出格式

Output $T$ lines. For each test case, output the minimum and maximum possible numbers of distinct syllables in $S$, in this order, separated by a space.

3
RaRa
ICPCJAG
BuRiShaBuShaBuRiBu

1 3
6 6
4 10

提示

In the first test case, the word “RaRa” can be divided into syllables in the following ways: “Ra” + “Ra”, “Ra” + “R” + “a”, “R” + “a” + “Ra”, and “R” + “a” + “R” + “a”. Here, + denotes string concatenation. For each division, the number of distinct syllables is $1$, $3$, $3$, and $2$, respectively. Therefore, the minimum is $1$ and the maximum is $3$.