Zhu and 772002

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

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

Sample Input

2 3 3 3 4 3 2 2 2

Sample Output

Case #1: 3 Case #2: 3

Hint

wange2014

Source

2016中国大学生程序设计竞赛 - 网络选拔赛

提交代码