Ternary Logic

We are well acquainted with "Boolean" logic, which operates on the set of just two values True and False. However it often feels as slightly insufficient for real-life use. Consider the following example:

Millionaire promises his son: if you pass university exams this year, and my business is not ruined meanwhile, I'll assign you as chief technical executive. On contrary, if you fail, I'll sell the business and retire. However it may happen that the son will marry some girl and quit university to pursue an artist career. Or the business in question may be acquired by some larger company - which prevent father from fulfilling either of his intentions.

How could we deal with such uncertainty? For example, how we use it in the expression ... you pass exam AND business NOT ruined... - some matematicians started to ponder on this perhaps century ago or more.

Popular approach is to introduce the third value Unknown (or Undefined, or Uncertain) and extend typical logical operations to accept it. Many variants define the basic operations like this:

     NOT        AND              OR             XOR

A    ~A     &F  &U  &T      |F  |U  |T      ^F  ^U  ^T

F     T      F   F   F       F   U   T       F   U   T

U     U      F   U   U       U   U   T       U   U   U

T     F      F   U   T       T   T   T       T   U   F

It is easy to calculate that total amount of possible binary operations is 3^9 = 19683 rather than 2^4 = 16 for Boolean logic. It is useless to try giving separate name or operator sign for each of them. Rather we can construct other operations using some basic ones.

However the operations mentioned above are not sufficient to construct any possible of other operations (can you see why?) We introduce yet another unary operation called cyclic negation using exclamation mark for it, like this:

!F is T     !U is F     !T is U

Problem statement

We want to construct several binary operations, represented by their "truth tables". Please construct suitable expressions in infix form, using variables A and B, basic operations mentioned above (~, !, &, |, ^) and parentheses as necessary. Binary operations have highest precedence for & and lowest for ^ while unary operations have priority above them. Constants F, U, T could be used also.

Input has a number in the first line - the number of lines with testcases, which are following. Every testcase consists of 9 letters split in three triplets for convenience. The first triplet is for A = F, the last for A = T. Letters in each triplet correspond to values of B running over F, U and T in order.

Answer should give corresponding amount of expressions, space separated.

Example:

input data:
3
TUF UUU FUT
FFF FFF UUU
TTT UTU FTU

answer:
~(A^B) (A&!A) ~(!B&A)