Chef has a string
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 stringusing the following operation:
- Select any such that and remove 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
abcde and we apply operation on , then becomes
Help Hitesh find the minimum number of operations required to reverse.
It is guaranteed that it is possible to reverse the string in a finite number of operations.
- The first line of input contains a single integer , denoting the number of test cases. The description of test cases follows.
- Each test case consists of a single line containing the string S.
For each test case, output the minimum number of operations required to reverse the string.
- Sum of over all testcases does not exceed .
Sample Input 1
2 abdeba codechef
Sample Output 1
- Test case-1: Following steps can be performed:
- Test case-2: following steps can be performed: