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.
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’.
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.
Input | Output |
---|---|
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. |