SHLIGHTS - Shifting Lights

no tags 

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


hide comments
nadstratosfer: 2021-06-05 01:41:34

Took me a while to figure out the logic, fun problem.

Malfple: 2014-08-24 12:55:23

find a way so your program run on O(n)

ishaan: 2014-01-12 13:47:00

I am getting TLE.I am just parsing the string once and then using an array of blues to determine the answer.Can someone please help?

Sardar Khan: 2012-08-08 21:48:06

Nice ques. ... :))

Zhiang: 2012-08-07 16:09:00

nice one....:)

ZODI91: 2012-07-27 20:21:59

Dont go for brute force..

! include(L.ppt): 2011-08-03 08:47:39

main problem is time limit.......


Added by:Paranoid Android
Date:2010-12-20
Time limit:0.300s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All