Square and Cube

The_Shaeekh Intra AUST Programming Co...
Limits 1s, 512 MB

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

InputOutput
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.

Submit

Login to submit.

Statistics

91% Solution Ratio
user.015414Earliest, 3M ago
prodip_bsmrstuFastest, 0.0s
user.015414Lightest, 131 kB
shakil07Shortest, 377B
Toph uses cookies. By continuing you agree to our Cookie Policy.