헤라클레스와 히드라

헤라클레스는 그리스 신화의 비극적인 영웅이다. 제우스의 사생아로 태어났고, 그래서 제우스의 아내 헤라는 그를 몹시 미워했다. 힘이 세고 지혜도 뛰어났지만, 광기에 사로잡히면 자기 아이와 스승, 연인까지 스스로 죽였다. 아이를 죽인 죄를 씻으려고 에우리스테우스 왕이 내린 12가지 과업을 수행한 인물로 잘 알려져 있다.

두 번째 과업은 머리가 여러 개 달린 거대한 히드라를 죽이는 것이었다. 이 히드라는 헤라가 헤라클레스를 죽이려고 만든 괴물이다.

히드라를 죽이기 어려운 이유는 머리 하나를 잘라내면 그 자리에서 새 머리가 2개 자라나기 때문이다. 머리가 하나라도 남아 있으면 히드라는 죽지 않는다. 헤라클레스의 조카 이올라우스는 머리를 자른 뒤 밑동을 불로 지지면 새 머리가 자라지 않는다는 사실을 알아냈다.

헤라클레스와 이올라우스는 행동을 순서대로 수행한다. 각 행동은 머리를 자르기만 하는 것과, 자른 뒤 밑동을 불로 지지는 것 둘 중 하나이다. 자르기만 하면 남은 머리 개수가 1 늘어나고, 자른 뒤 불로 지지면 1 줄어든다. 모든 행동이 끝난 뒤 히드라에게 남은 머리 개수를 구하여라.

첫째 줄에 데이터 세트의 개수 $K$가 주어진다.

각 데이터 세트의 첫째 줄에는 히드라의 머리 개수 $h$가 주어진다 ($1 \le h \le 50$).

둘째 줄에는 헤라클레스와 이올라우스의 행동이 길이 100 이하인 문자열로 주어진다. 'c'는 불로 지지지 않고 머리만 자르는 행동이고, 'b'는 머리를 자른 뒤 불로 지지는 행동이다.

히드라의 머리가 모두 없어진 뒤에는 더 이상 행동이 주어지지 않는다.

각 데이터 세트마다 첫째 줄에 Data Set x:를 출력한다. 여기서 $x$는 1부터 시작하는 데이터 세트 번호이다.

다음 줄에 모든 행동이 끝난 뒤 남아 있는 히드라의 머리 개수를 출력한다.

데이터 세트와 데이터 세트 사이에는 빈 줄을 하나 출력한다.