H. String Partition
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters.

The concatenation of a sequence of strings is the string that results from writing down these strings in the order they appear in the sequence. For example, the concatenation of the sequence ["code"$$$,$$$ "force"$$$,$$$ "s"] is the string "codeforces".

A partition of the string $$$s$$$ is a sequence $$$a$$$ of strings such that if we concatenate the strings in the sequence, the result will be the string $$$s$$$. Note that there may exists more than one possible partition of the string.

We call a partition of the string $$$s$$$ good if the following holds:

  • We say that a string $$$b$$$ is considered x-good (for some positive integer $$$x$$$) if for every English letter that appears in the string $$$b$$$, the number of appearances of this letter in $$$b$$$ is exactly $$$x$$$.
  • A partition is considered good if there exists an integer $$$x$$$ such that all strings in the partition are x-good.

The size of the partition is defined as the number of strings in that partition. Your task is to find the minimum size of a good partition.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — representing the number of testcases.

Each line of the next $$$t$$$ lines contains a string $$$s$$$ of length $$$|s|$$$ ($$$1 \le |s| \le 10^5$$$) — representing the string that is required to partition.

It's guaranteed that the sum of $$$|s|$$$ over all testcases doesn't exceed $$$10^5$$$.

Output

For each testcase, print a new line containing a single integer representing the minimum size of a good partition.

Example
Input
3
codeforces
acpc
aywwaaaaa
Output
2
2
6