NY10A - Penney Game

Penney’s game is a simple game typically played by two players.  One version of the game calls for each player to choose a unique three-coin sequence such as HEADS TAILS HEADS (HTH).  A fair coin is tossed sequentially some number of times until one of the two sequences appears.  The player who chose the first sequence to appear wins the game.

For this problem, you will write a program that implements a variation on the Penney Game.  You willread a sequence of 40 coin tosses and determine how many times each three-coin sequence appears.  Obviously there are eight such three-coin sequences: TTT, TTH, THT, THH, HTT, HTH, HHT and HHH. Sequences may overlap.  For example, if all 40 coin tosses are heads, then the sequence HHH appears 38 times.

Input

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow.  Each data set consists of 2 lines.  The first line contains the data set number N.  The second line contains the sequence of 40 coin tosses.  Each toss is represented as an upper case H or an upper case T, for heads or tails, respectively.  There will be no spaces on any input line.

Output

For each data set there is one line of output.  It contains the data set number followed by a single space, followed by the number of occurrences of each three-coin sequence, in the order shown above, with a space between each one.  There should be a total of 9 space separated decimal integers on each output line.

Example

Input:
4
1
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
2
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
3
HHTTTHHTTTHTHHTHHTTHTTTHHHTHTTHTTHTTTHTH
4
HTHTHHHTHHHTHTHHHHTTTHTTTTTHHTTTTHTHHHHT

Output:
1 0 0 0 0 0 0 0 38
2 38 0 0 0 0 0 0 0
3 4 7 6 4 7 4 5 1
4 6 3 4 5 3 6 5 6

Added by:John Mario
Date:2011-03-22
Time limit:0.800s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM Greater New York Regionals 2010

hide comments
2015-01-02 20:11:09 kanak thakkar
my 50th on spoj!! peice of cake
2015-01-01 06:11:14 :.Mohib.:
Silly mistakes coast me 4 WA......Finally AC....:)
2013-08-21 04:09:04 (Tjandra Satria Gunawan)(曾毅昆)
Exact judge is really annoying for this kind of problem :-P
2013-03-26 18:01:22 Akb
@Omar Ahmed: a coin toss can result in either a Head(H) or a Tail(T). Now for three coin tosses there are 8 permutations of results: TTT, TTH, THT, THH, HTT, HTH, HHT and HHH. so for N coins when tossed once you will get a sequence composed of T and H.
Now this problem: given a test case number and a sequence of H and T you have to find and print how many times each of those 8 sequences are contained in the given sequence.
2013-03-20 03:16:01 Omar Ahmed
srry but i REALLY cant understand the problem or understand the I/O .. so please if anyone can give me a little explanation for this problem ? ..
thanks in advance
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.