## LCPC12I - No more Johnny

no tags

```Description
Sure you are bored from Johnny and his stories, so we decided that we will not mention Johnny in this problem. As you are one of the cleverest students in programming course, it is required to develop a magic calculator. Magic calculators work on integer numbers and have two operations only: '&' (and) and '|' (or). As you know & and | operation works with bits so 3 & 2 will be 2 as 11 & 10 = 10 which is 2. But in our calculator & and | operation will have a different meaning. Every positive integer n > 1 can be represented in exactly one way as a product of prime (A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself) powers:

Where p1 < p2 < ... < pk are primes and the αi are positive integers; 1 is represented by the empty product. In this problem you will work with prime factors of numbers that is & means you will take minimum power for each prime between the 2 numbers unless prime exist in one and doesn't exist in the other in such case you will take the power of prime as it is,| you will take maximum power for each prime between the 2 numbers unless prime exist in one and doesn't exist in the other in such case you will take the power of prime as it is. For example 6 | 9 will be 21 * 31 | 33 so result will be 21 * 33 that will be 18. Also 6 & 9 will be 21 * 31 & 33 so result will be 21 * 31 that will be 6. Given a set of numbers and operations between them, print the final result as primes with powers (show prime factors of the result).
Input Format
The first line of input contains an integer T, the number of test cases. T test cases follows, the first line of each test case contains N where 1 <= N <= 100 represent number of integers to do calculations. Followed by N numbers between each 2 number one of the operations & or | (The precedence of & and | are equal and both are left associative). All numbers x will be 0 <= x < 100.
Output Format
There should be T lines, containing the following format.
k. p1^a1 p2^a2 ..pi^ai…pn^an
Where k is the test case number (starting at 1), a single period, a single space and sequence of primes with their powers represent a final result where p1 <p2 < pi < pn (don't print primes with power zero).

Sample Input

Sample Output

2
3
12 | 6 & 15
3
12 & 6 | 15

1. 2^2 3^1 5^1
2. 2^1 3^1 5^1

Sample Clarification:
12 | 6 & 15 means 22 * 31 | 21 * 31 & 31 * 51 that will be 22 * 31 & 31 * 51 that will be 22 * 31 * 51```