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 p₁ < p₂ < ... < p_k 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 2¹ * 3¹ | 3³ so result will be 2¹ * 3³ that will be 18. Also 6 & 9 will be 2¹ * 3¹ & 3³ so result will be 2¹ * 3¹ 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

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

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

Sample

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

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

Sample Clarification:

12 | 6 & 15 means 2² * 3¹ | 2¹ * 3¹ & 3¹ * 5¹ that will be 2² * 3¹ & 3¹ * 5¹ that will be 2² * 3¹ * 5¹