Coin Game

Interview

Time limit1sMemory limit128 MB

Summary
Count occurrences of each of 8 possible length-3 head/tail patterns among all consecutive triples in a 40-character coin toss string, for multiple test cases.
Level

Easy2 of 10

Topics
String, Implementation
Solved
No attempts yet

Problem

In this coin game, several players each choose one length-3 coin sequence. A 3-coin sequence is a length-3 sequence made of heads and tails. There are eight possible sequences: TTT, TTH, THT, THH, HTT, HTH, HHT, and HHH.

A judge tosses one coin 40 times and records the outcomes in order. From the recorded string, consider every consecutive block of three tosses and count how many times each 3-coin sequence appears. The player who chose the most frequent sequence wins.

Given the result of 40 coin tosses, compute the number of appearances of each 3-coin sequence. If all 40 tosses are H, then HHH appears 38 times.

Input

The first line contains the number of test cases P(1 ≤ P ≤ 1000). Each test case consists of one line containing the result of 40 coin tosses. Heads is written as H, and tails is written as T.

Output

For each test case, output how many times each 3-coin sequence appears. Print the counts in the order TTT, TTH, THT, THH, HTT, HTH, HHT, HHH, separated by spaces.

Examples1

  1. Example 1

    Input
    4
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
HHTTTHHTTTHTHHTHHTTHTTTHHHTHTTHTTHTTTHTH
HTHTHHHTHHHTHTHHHHTTTHTTTTTHHTTTTHTHHHHT
    Expected output
    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