Minimum Unique Substrings Partitioning

You are given a string s and your task is to partition it into the minimum number of substrings such that every substring consists of unique characters. In other words, while scanning the string from left to right, if you encounter a character that has already appeared in the current substring, you should end the current substring and start a new one beginning with that character.

Task: For a given string, determine the minimum number of substrings (or partitions) required so that no substring contains any duplicate characters.

Example:

• For s = "abac", the minimum partition is ["ab", "ac"]. So, the answer is 2.
• For s = "world", all characters are unique so the answer is 1.

Note: The algorithm should efficiently handle multiple test cases.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
s1
s2
...
sT

Where:

• T is the number of test cases.
• Each of the following T lines contains a string s that you need to partition.

outputFormat

For each test case, output a single integer on a new line which represents the minimum number of substrings the input string can be partitioned into so that all characters in each substring are unique. The output should be written to standard output (stdout).

## sample

3
abac
world
banana

2
1
3

</p>