Recently I made a new device. It contains a set of lightbulbs, each having two parts. The left part glows blue and the right part glows green. One cannot guess which parts of the bulbs will be  glowing when the device is powered on. Consider any two adjacent bulbs at time t. If the left bulb is glowing green and the right bulb is glowing blue they swap their states to blue and green respectively at time t + 1. But now I am wondering, if I power it on when will the bulbs stop swapping. Can you help me with this ?

Input

The first line of the input contains t, the number of testcases. Each of the next t lines contains a single string containing characters 'B' and 'G' representing the bulbs when switched on i.e. at time t = 0. Here 'B' is for blue and 'G' is for green. The length of the string will be less than 100000.

Output

For each test output one line giving the time after which swapping stops.

Example

Input :

2

GBGBBB

BGBBGGGBBBGBGB

Output :

4

8