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


hide comments
nitish rao: 2013-09-23 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: 2013-09-23 13:10:41
Francky: 2012-10-11 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.
>>> Tutorial for sure.

numerix: 2012-10-11 21:15:34

After several WAs I figured out that the contraints are wrong:
x will always be positive and less than 101.
The formatting of the input data seems okay, but nevertheless all my submissions lead to WA.
Could you please check submission 7833887.
Is the exact judge used here?

Last edit: 2012-10-11 21:17:14
Ikhaduri: 2012-10-11 14:09:49

What should we print if answer for the query is 1 or 0?

Xsquare: 2012-10-07 18:02:58

Its showing WA's again and again.. any tricky cases.. please tell?.. :(

Problem Solver: 2012-10-07 17:05:36

Cool task ;)


Added by:Gareev
Date:2012-10-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:LCPC 2012