Time travellers

In the world of magic there exist a gate to travel in time. Magical authority has appointed Alice to keep a record of all the people passing through that gate. Every time a person goes inside that gate Alice writes an ‘I’ in a paper and every time a person comes out of the gate Alice writes down ‘O’. Once, magical authority asked Alice about the number of peoples who have used that gate. Now looking at ‘I’ and ‘O’ at his paper it’s impossible to tell the exact number of peoples who have used that gate but he’s sure that there exist a method to know the minimum number of distinct peoples he could have seen passing through the gate. Can you write a code to know the minimum number of peoples he could have seen?

Input

First line of input contains a number T i.e. the number of test cases. Each of the next T lines contains a string S which is the record Alice has kept in his diary.

Output

Your code should print T lines each having one numbers, i.e. the minimum number of peoples he could have seen.

Constraints

1<=T<=100
1<=length of S<=1000

Time limit

1 second

Sample Input

2
IOIOI
OOO

Sample Output

1
3
#include<stdio.h>
void main()
{
int test,t,i,o,l,k,result;
char s[1050];
scanf("%d",&t);
for(test=0;test<t;test++)
  {
      i=o=k=result=0;
      scanf("%s",s);
       while(s[k]!='\0')
       {
        if(s[k]=='I')i++;
        if(s[k]=='O')o++;
        k++;
       }
  result=abs(i-o);
  if(result==0) 
  printf("%d\n",result+1);
  else
  printf("%d\n",result);
  }
}
//