Problem Description

In a string that contains only lowercase letters, a letter is called heavy if and only if it appears more than once in the string; otherwise, it is called light.

Given some strings, for each string, determine whether the heavy letters and light letters appear alternately. (That is, either every letter in an odd position is heavy and every letter in an even position is light, or every letter in an odd position is light and every letter in an even position is heavy.)

Input Format

The first line contains two positive integers $T$ and $N$, representing the number of strings and the length of each string.

The next $T$ lines each contain a string of length $N$ consisting of lowercase letters.

Output Format

Output $T$ lines, each containing a single character T or F. If in the $i$-th input string, the light letters and heavy letters appear alternately, output T on the $i$-th line; otherwise, output F.

3 4
abcb
bcbb
babc

T
F
T

2 3
abc
bcb

F
T

Hint

[Sample 1 Explanation]

The first string consists of light, heavy, light, heavy letters.

The second string ends with two consecutive heavy letters.

The third string consists of heavy, light, heavy, light letters.

[Sample 2 Explanation]

The first string consists entirely of light letters.

The second string consists of heavy, light, heavy letters.

[Constraints]

This problem uses bundled testdata.

For all testdata, the strings are guaranteed to contain only lowercase letters, $2\leq T\leq 10^4$, and $2\leq N\leq 100$.

The table below shows the allocation of the $15$ points:

Translated by ChatGPT 5