The New Cow Dance

The (Female) cows are designing a new dance technique and have
recruited the (Male) bulls to dance with them. The dance requires
all N (1 <= N <= 30,000) of the cows and bulls to arrange themselves
in a circle, head-to-tail. A circle is described by listing the
gender of the northern-most cow and then subsequently the gender
of each cow going clockwise around the circle until all cows are
listed once; this description is called a "circle".

A "dance arc of length N" starts at any cow in the circle and lists
the genders of that cow and the subsequent cows in clockwise order
until N cows have been named. For example, the circle of cows listed
as "FMFFM" has 5 length-3 dance arcs: "FMF", "MFF", "FFM", "FMF"
and "MFM" (they are not distinct, but they differ by their starting
position in the dance circle).

A proper dance circle requires an acceptable number of bulls and
cows. The required property for any dance circle is that for every
arc-length between 1 and N inclusive, the count of males in any two
arcs of the same length never varies by more than one (a property
which will also hold for the count of the number of females).

The dance circle listed as "MMFFMFF" is not a proper one since the
length-5 dance arcs "MMFFM" (from position 1) and "FFMFF" (from
position 3) have 2 and 4 "F"s respectively, so the difference in
their number of "F"s is 2.

Similarly, "FMFMFFMFFM" does not describe a proper dance circle
because it contains length-5 dance arc "FFMFF" (from position 5)
and "MFMFM", (from position 15) and the difference in their number
of "F"s is greater than 1.

Both the dance lists "FMF" and "FFMFMFFM" are proper dance circles;
see for yourself.

Given D (1 <= D <= 10) dance circular listings, determine whether
they are proper dance circles.

PROBLEM NAME: dcircle

INPUT FORMAT:

* Line 1: A single integer: D

* Lines 2..D+1: Line i+1 contains dance listing i.

SAMPLE INPUT (file dcircle.in):

4
MMFFMFF
FMFMFFMFFM
FMF
FFMFMFFM

OUTPUT FORMAT:

* Lines 1..D: Line i contains 1 if the dance listing i is a proper
        dance layout or 0 otherwise.

SAMPLE OUTPUT:

0
0
1
1