Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

FFT

By tufaan · Limits 2s, 512 MB

Full form of FFT is Fast Fourier Transformation. Fast Fourier Transformations are widely used for many applications in engineering, science, and mathematics. The basic ideas were popularized in 1965. In 1994, Gilbert Strang described the FFT as “the most important numerical algorithm of our lifetime”. It is one of the complex algorithm to understand.

But today your task is a simple one. You are here to help little Emma. Her teacher had given her a list of N strings and told her to find the full form of FFT. She doesn’t know the full form of FFT. So she decides to write down those consecutive strings which contain ‘F’,‘F’,‘T’ as first letters. As N can be very large, Emma hired you to write a program that will complete her task.

Input

The first line of the input contains a single integer t (1 ≤ t ≤ 100), denoting the number of test cases.

Each test case contains a number N (0 ≤ N ≤ 1000) and next N line follows. Each line contains a string (length of string ≤ 10) . It’s guaranteed that first character of each string is always ‘F’ or ‘T’.

Output

For each test case you have to print the total number of full forms (let it be V) in a single line. Then print V.

lines, the possible full forms of FFT. The strings should be separated by a single blank space. Read sample Input/Output for better understanding.

Sample

InputOutput
2
7
Fast
Fourier
Transforms
Foo
Fnaarj
Fujura
Tanfu
5
Tasin
Fast
Tyll
Trrei
Fun
2
Fast Fourier Transforms
Fnaarj Fujura Tanfu
0

In first test case, we can see FFT in the 1st, 2nd and 3rd string: Fast, Fourier, Transforms. And again in the 5th, 6th and 7th string: Fnaarj, Fujura, Tanfu.

In second test case, there are no such consecutive strings that can form FFT.


    Discussion

    Statistics


    95% Solution Ratio

    NAbdullaEarliest, Jan '18

    MutasimFastest, 0.0s

    BruteforcekidLightest, 524 kB

    joe.masterShortest, 205B

    Submit

    Login to submit