시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 416 362 337 89.153%

문제

동전게임은 주로 두 사람이 함께 즐기는 게임이다. 이 중 3-동전게임은 여러 명이 할 수 있는 게임이다. 각 사람은 각각 3-동전수열 중 하나를 선택한다. 3-동전수열이랑 앞 뒤 앞과 같은 수열이고, 8가지(뒤뒤뒤,뒤뒤앞,뒤앞뒤,뒤앞앞,앞뒤뒤,앞뒤앞,앞앞뒤,앞앞앞)가 있다.

이제 심판은 동전 1개를 40번 던진다. 그 다음 심판은 동전이 앞인지 뒤인지를 던진 순서대로 종이에 적는다. 그 다음 3-동전수열이 각각 몇 번씩 나왔는지 기록한다. 가장 많이 나온 수열을 선택한 사람이 이긴다.

동전 40번 던진 결과가 주어졌을 때, 3-동전수열이 각각 몇 번 나왔는지를 출력하는 프로그램을 작성하시오. 예를 들어, 40개의 동전이 모두 앞면일 경우 앞앞앞은 38번 나타난다.

입력

첫째 줄에 테스트 케이스의 개수 P(1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 동전을 40번 던진 결과가 주어진다. 이 때, 앞면은 H로, 뒷면은 T로 표현한다. 

출력

각 테스트 케이스마다 3-동전수열이 몇 번 나타났는지를 출력한다. 뒤뒤뒤, 뒤뒤앞, 뒤앞뒤, 뒤앞앞, 앞뒤뒤, 앞뒤앞, 앞앞뒤, 앞앞앞 순서대로 공백으로 구분해서 출력한다.

예제 입력 1

4
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
HHTTTHHTTTHTHHTHHTTHTTTHHHTHTTHTTHTTTHTH
HTHTHHHTHHHTHTHHHHTTTHTTTTTHHTTTTHTHHHHT

예제 출력 1

0 0 0 0 0 0 0 38
38 0 0 0 0 0 0 0
4 7 6 4 7 4 5 1
6 3 4 5 3 6 5 6
W3sicHJvYmxlbV9pZCI6IjI2ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzZDlcdWM4MDQgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWIzZDlcdWM4MDRcdWFjOGNcdWM3ODRcdWM3NDAgXHVjOGZjXHViODVjIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkNTY4XHVhZWQ4IFx1Yzk5MFx1YWUzMFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWM5MTEgMy1cdWIzZDlcdWM4MDRcdWFjOGNcdWM3ODRcdWM3NDAgXHVjNWVjXHViN2VjIFx1YmE4NVx1Yzc3NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NDAgXHVhYzAxXHVhYzAxIDMtXHViM2Q5XHVjODA0XHVjMjE4XHVjNWY0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTVjXHViMmU0LiAzLVx1YjNkOVx1YzgwNFx1YzIxOFx1YzVmNFx1Yzc3NFx1Yjc5MSBcdWM1NWUgXHViNGE0IFx1YzU1ZVx1YWNmYyBcdWFjMTlcdWM3NDAgXHVjMjE4XHVjNWY0XHVjNzc0XHVhY2UwLCA4XHVhYzAwXHVjOWMwKFx1YjRhNFx1YjRhNFx1YjRhNCxcdWI0YTRcdWI0YTRcdWM1NWUsXHViNGE0XHVjNTVlXHViNGE0LFx1YjRhNFx1YzU1ZVx1YzU1ZSxcdWM1NWVcdWI0YTRcdWI0YTQsXHVjNTVlXHViNGE0XHVjNTVlLFx1YzU1ZVx1YzU1ZVx1YjRhNCxcdWM1NWVcdWM1NWVcdWM1NWUpXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0XHVjODFjIFx1YzJlY1x1ZDMxMFx1Yzc0MCBcdWIzZDlcdWM4MDQgMVx1YWMxY1x1Yjk3YyA0MFx1YmM4OCBcdWIzNThcdWM5YzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjMmVjXHVkMzEwXHVjNzQwIFx1YjNkOVx1YzgwNFx1Yzc3NCBcdWM1NWVcdWM3NzhcdWM5YzAgXHViNGE0XHVjNzc4XHVjOWMwXHViOTdjIFx1YjM1OFx1YzljNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODg1XHVjNzc0XHVjNWQwIFx1YzgwMVx1YjI5NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyAzLVx1YjNkOVx1YzgwNFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWFjMDFcdWFjMDEgXHViYTg3IFx1YmM4OFx1YzUyOSBcdWIwOThcdWM2NTRcdWIyOTRcdWM5YzAgXHVhZTMwXHViODVkXHVkNTVjXHViMmU0LiBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzc0IFx1YjA5OFx1YzYyOCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM3NzRcdWFlMzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjNkOVx1YzgwNCA0MFx1YmM4OCBcdWIzNThcdWM5YzQgXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIDMtXHViM2Q5XHVjODA0XHVjMjE4XHVjNWY0XHVjNzc0IFx1YWMwMVx1YWMwMSBcdWJhODcgXHViYzg4IFx1YjA5OFx1YzY1NFx1YjI5NFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgNDBcdWFjMWNcdWM3NTggXHViM2Q5XHVjODA0XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWM1NWVcdWJhNzRcdWM3N2MgXHVhY2JkXHVjNmIwIFx1YzU1ZVx1YzU1ZVx1YzU1ZVx1Yzc0MCAzOFx1YmM4OCBcdWIwOThcdWQwYzBcdWIwOWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFAoMSAmbGU7IFAgJmxlOyAxMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHViM2Q5XHVjODA0XHVjNzQ0IDQwXHViYzg4IFx1YjM1OFx1YzljNCBcdWFjYjBcdWFjZmNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWM1NWVcdWJhNzRcdWM3NDAgSFx1Yjg1YywgXHViNGI3XHViYTc0XHVjNzQwIFRcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IDMtXHViM2Q5XHVjODA0XHVjMjE4XHVjNWY0XHVjNzc0IFx1YmE4NyBcdWJjODggXHViMDk4XHVkMGMwXHViMGFjXHViMjk0XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViNGE0XHViNGE0XHViNGE0LCBcdWI0YTRcdWI0YTRcdWM1NWUsIFx1YjRhNFx1YzU1ZVx1YjRhNCwgXHViNGE0XHVjNTVlXHVjNTVlLCBcdWM1NWVcdWI0YTRcdWI0YTQsIFx1YzU1ZVx1YjRhNFx1YzU1ZSwgXHVjNTVlXHVjNTVlXHViNGE0LCBcdWM1NWVcdWM1NWVcdWM1NWUgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NzRcdWMxMWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI2ODQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQZW5uZXkgR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+UGVubmV5JnJzcXVvO3MgZ2FtZSBpcyBhIHNpbXBsZSBnYW1lIHR5cGljYWxseSBwbGF5ZWQgYnkgdHdvIHBsYXllcnMuIE9uZSB2ZXJzaW9uIG9mIHRoZSBnYW1lIGNhbGxzIGZvciBlYWNoIHBsYXllciB0byBjaG9vc2UgYSB1bmlxdWUgdGhyZWUtY29pbiBzZXF1ZW5jZSBzdWNoIGFzIEhFQURTIFRBSUxTIEhFQURTIChIVEgpLiBBIGZhaXIgY29pbiBpcyB0b3NzZWQgc2VxdWVudGlhbGx5IHNvbWUgbnVtYmVyIG9mIHRpbWVzIHVudGlsIG9uZSBvZiB0aGUgdHdvIHNlcXVlbmNlcyBhcHBlYXJzLiBUaGUgcGxheWVyIHdobyBjaG9zZSB0aGUgZmlyc3Qgc2VxdWVuY2UgdG8gYXBwZWFyIHdpbnMgdGhlIGdhbWUuPFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGltcGxlbWVudHMgYSB2YXJpYXRpb24gb24gdGhlIFBlbm5leSBHYW1lLiBZb3Ugd2lsbCByZWFkIGEgc2VxdWVuY2Ugb2YgNDAgY29pbiB0b3NzZXMgYW5kIGRldGVybWluZSBob3cgbWFueSB0aW1lcyBlYWNoIHRocmVlLWNvaW4gc2VxdWVuY2UgYXBwZWFycy4gT2J2aW91c2x5IHRoZXJlIGFyZSBlaWdodCBzdWNoIHRocmVlLWNvaW4gc2VxdWVuY2VzOiBUVFQsIFRUSCwgVEhULCBUSEgsIEhUVCwgSFRILCBISFQgYW5kIEhISC4gU2VxdWVuY2VzIG1heSBvdmVybGFwLiBGb3IgZXhhbXBsZSwgaWYgYWxsIDQwIGNvaW4gdG9zc2VzIGFyZSBoZWFkcywgdGhlbiB0aGUgc2VxdWVuY2UgSEhIIGFwcGVhcnMgMzggdGltZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICgxICZsZTsgUCAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBjb25zaXN0cyBvZiAyIGxpbmVzLiBUaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgZGF0YSBzZXQgbnVtYmVyIE4uIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyB0aGUgc2VxdWVuY2Ugb2YgNDAgY29pbiB0b3NzZXMuIEVhY2ggdG9zcyBpcyByZXByZXNlbnRlZCBhcyBhbiB1cHBlciBjYXNlIEggb3IgYW4gdXBwZXIgY2FzZSBULCBmb3IgaGVhZHMgb3IgdGFpbHMsIHJlc3BlY3RpdmVseS4gVGhlcmUgd2lsbCBiZSBubyBzcGFjZXMgb24gYW55IGlucHV0IGxpbmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQgdGhlcmUgaXMgb25lIGxpbmUgb2Ygb3V0cHV0LiBJdCBjb250YWlucyB0aGUgZGF0YSBzZXQgbnVtYmVyIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlLCBmb2xsb3dlZCBieSB0aGUgbnVtYmVyIG9mIG9jY3VycmVuY2VzIG9mIGVhY2ggdGhyZWUtY29pbiBzZXF1ZW5jZSwgaW4gdGhlIG9yZGVyIHNob3duIGFib3ZlLCB3aXRoIGEgc3BhY2UgYmV0d2VlbiBlYWNoIG9uZS4gVGhlcmUgc2hvdWxkIGJlIGEgdG90YWwgb2YgOSBzcGFjZSBzZXBhcmF0ZWQgZGVjaW1hbCBpbnRlZ2VycyBvbiBlYWNoIG91dHB1dCBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==