Chef has a string SS consisting only of English lowercase letters (a – z). However, Hitesh does not like it and wants it to be reversed.

Hitesh wonders what is the minimum number of operations required to reverse the string SS using the following operation:

• Select any ii such that 1≤i≤|S|1≤i≤|S| and remove SiSi from its original position and append it to the end of the string (i.e. shift any character to the end of the string).

For e.g. if S=S= abcde and we apply operation on i=2i=2, then SS becomes acdeb.

Help Hitesh find the minimum number of operations required to reverse SS.

It is guaranteed that it is possible to reverse the string in a finite number of operations.

Input Format

• The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
• Each test case consists of a single line containing the string S.

Output Format

For each test case, output the minimum number of operations required to reverse the string SS.

Constraints

• 1≤T≤1031≤T≤103
• 1≤|S|≤1051≤|S|≤105
• Sum of |S||S| over all testcases does not exceed 2⋅1052⋅105.

Sample Input 1 

2
abdeba
codechef

Sample Output 1 

3
7

Explanation

• Test case-1: Following steps can be performed:

1. abdeba→abebadabdeba→abebad
2. abebad→abeadbabebad→abeadb
3. abeadb→abedbaabeadb→abedba

• Test case-2: following steps can be performed:

1. codechef→codechfecodechef→codechfe
2. codechfe→codecfehcodechfe→codecfeh
3. codecfeh→codefehccodecfeh→codefehc
4. codefehc→codfehcecodefehc→codfehce
5. codfehce→cofehcedcodfehce→cofehced
6. cofehced→cfehcedocofehced→cfehcedo
7. cfehcedo→fehcedoc

8. For Solution

   Click Here!