Problem Description

Zhu and 772002 are both good at math. One day, Zhu wants to test the ability of 772002, so he asks 772002 to solve a math problem.

But 772002 has a appointment with his girl friend. So 772002 gives this problem to you.

There are $n$ numbers $a_1, a_2, ..., a_n$. The value of the prime factors of each number does not exceed $2000$, you can choose at least one number and multiply them, then you can get a number $b$.

How many different ways of choices can make $b$ is a perfect square number. The answer maybe too large, so you should output the answer modulo by $1000000007$.

Input

First line is a positive integer $T$ , represents there are $T$ test cases.

For each test case:

First line includes a number $n(1 \leq n \leq 300)$，next line there are $n$ numbers $a_1, a_2, ..., a_n, (1 \leq a_i \leq 10^{18})$.

Output

For the i-th test case , first output Case #i: in a single line.

Then output the answer of i-th test case modulo by $1000000007$.

2
3
3 3 4
3
2 2 2

Case #1:
3
Case #2:
3

Author

UESTC