Girls' Party

Issac H. Ives는 여자아이들을 위해 파티를 열었다. 그는 좋은 물건을 몇 개 가지고 있었고, 그것을 여자아이들에게 선물로 나눠 주려 했다. 하지만 선물의 수가 충분하지 않아서 누가 가질지 정해야 했다. 그래서 그는 게임을 열었다.

게임에 앞서 Issac은 여자아이들을 두 팀으로 나눴다. 그의 친한 친구인 Bella와 Gabriella를 두 팀장으로 정하고, 나머지 여자아이들에게 Bella나 Gabriella 중 한 명에게 가도록 했다. 두 팀이 만들어진 뒤, Issac은 여자아이들에게 하나의 큰 원을 만들게 했다.

게임의 규칙은 다음과 같았다. 게임은 여러 라운드로 이루어졌다. 각 라운드에서 여자아이들은 시계 방향으로 1부터 N까지 수를 외쳤다(N은 게임이 시작되기 전에 정해진 수). N을 외친 여자아이에게 원 밖으로 나가라고 했고, 그 아이는 남은 게임에서 제외되었다. 그러면 다음 라운드는 그다음 여자아이부터 시작되었다. 즉, 여자아이들은 다시 수를 외쳤고, N을 외친 아이가 원을 떠났다. 어느 한 팀의 구성원만 남을 때까지 이것이 반복되었다. 남은 팀이 게임에서 이겼다.

게임이 진행되면서 Bella는 자기 팀의 여자아이가 Gabriella 팀보다 훨씬 많이 제외되는 것을 발견했다. Bella는 이에 불만을 품고 Issac에게 다음 라운드를 1 대신 0부터 세기 시작하게 해 달라고 요청했다. Issac은 컴퓨터 과학자였기 때문에 그녀의 생각이 마음에 들었고, 요청을 받아들였다. 그 라운드 이후 Gabriella 팀의 여자아이들이 많이 원을 떠났고, 결국 Bella 팀이 게임에서 이겨 Issac에게 선물을 받았다.

이제 다음과 같은 상황을 생각해 보자. Bella와 Gabriella가 각각 이끄는 두 팀이 있고, 두 팀의 구성원 수가 꼭 같지는 않다. Bella는 최대 한 라운드에서 시작 수를 1에서 0으로 바꿀 수 있다(시작하는 여자아이가 자기 팀인지와 상관없다). 원 안에 최대 몇 명의 Bella 팀 여자아이가 남을 수 있는지 알고 싶다. 이 문제를 해결하는 프로그램을 작성하라.

입력은 여러 데이터셋으로 이루어진다. 입력의 첫 줄에는 데이터셋의 수가 주어진다. 데이터셋의 수는 200을 넘지 않는다.

각 데이터셋은 양의 정수 N (1 ≤ N ≤ 230)과 여자아이들의 시계 방향 순서를 나타내는 문자열로 이루어진다. 문자열의 각 문자는 ‘B’(Bella 팀의 구성원) 또는 ‘G’(Gabriella 팀)이다. 첫 라운드는 문자열의 첫 문자에 해당하는 여자아이부터 시작된다. 문자열의 길이는 2 이상 200 이하다.

각 데이터셋마다 원 안에 남을 수 있는 Bella 팀 여자아이의 최대 수를 한 줄에 출력한다. Bella 팀이 게임에서 이길 방법이 없으면 “0”(따옴표 제외)을 출력한다.