BlackPanther wishes to do business of juicy fruits along India Pakistan border.
He is little weird so he crosses the border and pays fine.
Normally he just does business either on Indian side or on Pakistan side and sometimes crosses the border and pays fine. He is not asked to pay fine even if he stands at the gate.
Border is made up of electric fence and it is only possible to cross border through gates.
The border is represented by a line x = y on graph. Points starting from (1,1) , (2,2) , (3,3) ... (K,K) are gates.

BlackPanther is initially at (0,0) position. Movement is denoted by u (up) and r (right). One u means one unit upwards in graph and one r means one unit towards right in graph.
You have to tell how many times he will have to give fine to authorities.

Input:

The first line of input contains an integer T denoting the number of test cases.
For each test case, the first line contains a string of u’s and r’s for the movement of BlackPanther.

Output:

Print One number denoting the number of times BlackPanther had to pay fine.

Constraints:

• 1 ≤ T ≤ 20
• 1≤ Length of String ≤ 100000