LCPC12I  No more Johnny
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 p_{1} < p_{2} < ... < 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^{1 }* 3^{1}  3^{3} so result will be 2^{1 }* 3^{3} that will be 18. Also 6 & 9 will be 2^{1 }* 3^{1} & 3^{3} so result will be 2^{1 }* 3^{1} 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 2^{2} * 3^{1}  2^{1} * 3^{1} & 3^{1} * 5^{1} that will be 2^{2} * 3^{1} & 3^{1} * 5^{1} that will be 2^{2} * 3^{1} * 5^{1}
hide comments
nitish rao:
20130923 13:10:20
Whats the value for 0  0 ?? and How to print if answer is '0' or '1'? I was printing an empty line. Correct me if I am wrong. Last edit: 20130923 13:10:41 

Francky:
20121011 21:27:28
I didn't test this problem, but I ever post a comment to say that this one belongs to tutorial. You don't have to delete those kind of comments. My opinion is clear regarding constraints and interest.


numerix:
20121011 21:15:34
After several WAs I figured out that the contraints are wrong:


Ikhaduri:
20121011 14:09:49
What should we print if answer for the query is 1 or 0? 

Xsquare:
20121007 18:02:58
Its showing WA's again and again.. any tricky cases.. please tell?.. :( 

Problem Solver:
20121007 17:05:36
Cool task ;) 
Added by:  Gareev 
Date:  20121006 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  LCPC 2012 