시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 454 397 371 89.398%

문제

동전게임은 주로 두 사람이 함께 즐기는 게임이다. 이 중 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+XHJcblx0XHVjNzc0XHVjODFjIFx1YzJlY1x1ZDMxMFx1Yzc0MCBcdWIzZDlcdWM4MDQgMVx1YWMxY1x1Yjk3YyA0MFx1YmM4OCBcdWIzNThcdWM5YzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjMmVjXHVkMzEwXHVjNzQwIFx1YjNkOVx1YzgwNFx1Yzc3NCBcdWM1NWVcdWM3NzhcdWM5YzAgXHViNGE0XHVjNzc4XHVjOWMwXHViOTdjIFx1YjM1OFx1YzljNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODg1XHVjNzc0XHVjNWQwIFx1YzgwMVx1YjI5NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyAzLVx1YjNkOVx1YzgwNFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWFjMDFcdWFjMDEgXHViYTg3IFx1YmM4OFx1YzUyOSBcdWIwOThcdWM2NTRcdWIyOTRcdWM5YzAgXHVhZTMwXHViODVkXHVkNTVjXHViMmU0LiBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzc0IFx1YjA5OFx1YzYyOCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM3NzRcdWFlMzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjNkOVx1YzgwNCA0MFx1YmM4OCBcdWIzNThcdWM5YzQgXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIDMtXHViM2Q5XHVjODA0XHVjMjE4XHVjNWY0XHVjNzc0IFx1YWMwMVx1YWMwMSBcdWJhODcgXHViYzg4IFx1YjA5OFx1YzY1NFx1YjI5NFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgNDBcdWFjMWNcdWM3NTggXHViM2Q5XHVjODA0XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWM1NWVcdWJhNzRcdWM3N2MgXHVhY2JkXHVjNmIwIFx1YzU1ZVx1YzU1ZVx1YzU1ZVx1Yzc0MCAzOFx1YmM4OCBcdWIwOThcdWQwYzBcdWIwOWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFAoMSAmbGU7IFAgJmxlOyAxMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHViM2Q5XHVjODA0XHVjNzQ0IDQwXHViYzg4IFx1YjM1OFx1YzljNCBcdWFjYjBcdWFjZmNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzU1ZVx1YmE3NFx1Yzc0MCBIXHViODVjLCBcdWI0YjdcdWJhNzRcdWM3NDAgVFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgMy1cdWIzZDlcdWM4MDRcdWMyMThcdWM1ZjRcdWM3NzQgXHViYTg3IFx1YmM4OCBcdWIwOThcdWQwYzBcdWIwYWNcdWIyOTRcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI0YTRcdWI0YTRcdWI0YTQsIFx1YjRhNFx1YjRhNFx1YzU1ZSwgXHViNGE0XHVjNTVlXHViNGE0LCBcdWI0YTRcdWM1NWVcdWM1NWUsIFx1YzU1ZVx1YjRhNFx1YjRhNCwgXHVjNTVlXHViNGE0XHVjNTVlLCBcdWM1NWVcdWM1NWVcdWI0YTQsIFx1YzU1ZVx1YzU1ZVx1YzU1ZSBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU3NFx1YzExYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjY4NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBlbm5leSBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5QZW5uZXkmcnNxdW87cyBnYW1lIGlzIGEgc2ltcGxlIGdhbWUgdHlwaWNhbGx5IHBsYXllZCBieSB0d28gcGxheWVycy4gT25lIHZlcnNpb24gb2YgdGhlIGdhbWUgY2FsbHMgZm9yIGVhY2ggcGxheWVyIHRvIGNob29zZSBhIHVuaXF1ZSB0aHJlZS1jb2luIHNlcXVlbmNlIHN1Y2ggYXMgSEVBRFMgVEFJTFMgSEVBRFMgKEhUSCkuIEEgZmFpciBjb2luIGlzIHRvc3NlZCBzZXF1ZW50aWFsbHkgc29tZSBudW1iZXIgb2YgdGltZXMgdW50aWwgb25lIG9mIHRoZSB0d28gc2VxdWVuY2VzIGFwcGVhcnMuIFRoZSBwbGF5ZXIgd2hvIGNob3NlIHRoZSBmaXJzdCBzZXF1ZW5jZSB0byBhcHBlYXIgd2lucyB0aGUgZ2FtZS48XC9wPlxyXG5cclxuPHA+Rm9yIHRoaXMgcHJvYmxlbSwgeW91IHdpbGwgd3JpdGUgYSBwcm9ncmFtIHRoYXQgaW1wbGVtZW50cyBhIHZhcmlhdGlvbiBvbiB0aGUgUGVubmV5IEdhbWUuIFlvdSB3aWxsIHJlYWQgYSBzZXF1ZW5jZSBvZiA0MCBjb2luIHRvc3NlcyBhbmQgZGV0ZXJtaW5lIGhvdyBtYW55IHRpbWVzIGVhY2ggdGhyZWUtY29pbiBzZXF1ZW5jZSBhcHBlYXJzLiBPYnZpb3VzbHkgdGhlcmUgYXJlIGVpZ2h0IHN1Y2ggdGhyZWUtY29pbiBzZXF1ZW5jZXM6IFRUVCwgVFRILCBUSFQsIFRISCwgSFRULCBIVEgsIEhIVCBhbmQgSEhILiBTZXF1ZW5jZXMgbWF5IG92ZXJsYXAuIEZvciBleGFtcGxlLCBpZiBhbGwgNDAgY29pbiB0b3NzZXMgYXJlIGhlYWRzLCB0aGVuIHRoZSBzZXF1ZW5jZSBISEggYXBwZWFycyAzOCB0aW1lcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LiBFYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIDIgbGluZXMuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBkYXRhIHNldCBudW1iZXIgTi4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIHRoZSBzZXF1ZW5jZSBvZiA0MCBjb2luIHRvc3Nlcy4gRWFjaCB0b3NzIGlzIHJlcHJlc2VudGVkIGFzIGFuIHVwcGVyIGNhc2UgSCBvciBhbiB1cHBlciBjYXNlIFQsIGZvciBoZWFkcyBvciB0YWlscywgcmVzcGVjdGl2ZWx5LiBUaGVyZSB3aWxsIGJlIG5vIHNwYWNlcyBvbiBhbnkgaW5wdXQgbGluZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCB0aGVyZSBpcyBvbmUgbGluZSBvZiBvdXRwdXQuIEl0IGNvbnRhaW5zIHRoZSBkYXRhIHNldCBudW1iZXIgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIGZvbGxvd2VkIGJ5IHRoZSBudW1iZXIgb2Ygb2NjdXJyZW5jZXMgb2YgZWFjaCB0aHJlZS1jb2luIHNlcXVlbmNlLCBpbiB0aGUgb3JkZXIgc2hvd24gYWJvdmUsIHdpdGggYSBzcGFjZSBiZXR3ZWVuIGVhY2ggb25lLiBUaGVyZSBzaG91bGQgYmUgYSB0b3RhbCBvZiA5IHNwYWNlIHNlcGFyYXRlZCBkZWNpbWFsIGludGVnZXJzIG9uIGVhY2ggb3V0cHV0IGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d