Turja is thinking of preparing a hard problem for intra AUST programming contest. He asked Alam and Shoaib for ideas. After putting a lot of effort, Alam, also known as a prominent thinker, proposed that providing prime factorization of a number, the task is to find out if the number is prime. Then, Shoaib suggested that it would be more interesting to find out if the number’s a cube.
Finally, hearing from both them, Turja, man of wisdom decided to come up with a new problem. Eventually it became a easy one. The problem’s described below-
Given the prime factorization of a number, you have to find out if the number is both a square and a cube number.
Input
The first line contains an integer T denoting the number of test cases. Each of the test cases starts with an integer N indicating the number of primes the factorization has. The second line contains N pair of integers; each odd positioned integer’s one of the prime numbers of the factorization (consider the position of first integer is one). Finally, each even positioned integer is the the power of it’s previous integer.
Let’s say the number is 12. The prime factorization of 12 is (2^2)*(3^1). So, the input will look like: 2 2 3 1.
Constraints:
1 ≤ T ≤ 1000
1 ≤ N ≤ 100
No prime number and its power will be more than 10^6
Output
For each test case, output a single line “Case N: The number is both square and cube.” (without quotation) if the given number is both square and cube and “Case N: The number does not meet expectation.” (without quotation) otherwise, where N is the test number (starting from 1). See examples for clarification.
Sample
| Input | Output |
|---|---|
5 1 19 19 2 5 28 47 484 1 49 1152 5 3 484 5 193 53 22 67 61 2 3 1 2 6 | Case 1: The number does not meet expectation. Case 2: The number does not meet expectation. Case 3: The number is both square and cube. Case 4: The number does not meet expectation. Case 5: The number is both square and cube. |
