알파벳 문자열

알파벳 대문자로만 이루어진 문자열 $S$가 있고, 길이는 $N$이다. $S[i]$는 $S$의 $i$번째 문자를, $S[i:j]$는 $S[i], S[i+1], \ldots, S[j-1], S[j]$에 해당하는 $S$의 부분 문자열을 나타낸다. 이 문제에서 문자열의 인덱스는 1부터 시작한다.

$U(i, j)$는 $S[i:j]$에 나타나는 알파벳을 순서대로 정렬한 문자열이며, 중복해서 나타나는 알파벳은 제외한다.

예를 들어 $S = \text{"ABCBA"}$인 경우 $U(1, 3) = \text{"ABC"}$, $U(2, 4) = \text{"BC"}$, $U(1, 5) = \text{"ABC"}$이다.

모든 $1 \le i \le j \le N$에 대하여 $U(i, j)$를 구했을 때, 이 문자열 중에서 서로 다른 문자열이 모두 몇 개인지 구해보자.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 문자열 $S$가 주어진다.

각 테스트 케이스에 대해서 $U(i, j)$에 서로 다른 문자열이 몇 개 있는지 출력한다.

• $1 \le T \le 10$
• $1 \le N \le 100,000$

두 번째 예제의 경우 A, B, C, AB, BC, ABC 총 여섯 개의 문자열이 존재한다.

세 번째 예제의 경우 A, B, AB 총 세 개의 문자열이 존재한다.