QUEUES
------

One day, you overhear a conversation between Peep and Teet:

Peep:  I was Googling a problem I'm working on, and I found this 
algorithm written in pseudocode, but I'm not sure if it's exactly
right.

Teet:  Why not just implement it, run it and see?

Peep:  I did that.  It worked for some small inputs, but I'm
interested in seeing what it does for large inputs.  And it
just took too long when I tried to run it on a large input.

At this point, you peep over Peep's shoulder to look at the code.
This is what you see:

XYZ(A[1..n] : array of characters) : boolean
   precondition:  each element of A[i] is an upper-case letter
   Q : FIFO queue (initially empty)
   x,y : character
   i : integer

   for i <- 1..n
      Q.enqueue(A[i])
   end for
   Q.enqueue('@')      
   y <- 'A'
   loop
      x <- Q.dequeue()
      if x = 'Z' then
         return (Q.dequeue() = '@')
      end if
      loop until y = 'Z'
         y <- Q.dequeue()
         if y = '@' then 
            return false
         end if
         Q.enqueue(y)
      end loop
      if Q.dequeue() != x then 
         return false
      end if
      loop until y = '@'
         y <- Q.dequeue()
	 Q.enqueue(y)
      end loop
   end loop
end XYZ

After 3 minutes, you say:  That algorithm is terrible.  It's even 
worse than what you usually find when you Google for answers to
questions.  But I can write a programme that will produce the
same output much faster.

INPUT
-----

The input will consist of multiple instances.  The first line will 
contain a positive integer k giving the number of input instances.

Each input instance will be given on two lines as follows.
First, there will be an non-negative integer n on a line by itself.
The value of n will be at most 200000.  On the next line, there 
will be n upper-case letters separated by spaces, giving the 
entries of A[1..n].

OUTPUT
------

For each instance, output the value returned by XYZ(A[1..n]) on a
separate line.

SAMPLE INPUT
------------

3
2
Z Z
3
X Z X
6
X Z X Z X Z

SAMPLE OUTPUT
-------------

false
true
false