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 a1,a2,...,an. 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.

 

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

For each test case:

First line includes a number n(1≤n≤300)，next line there are n numbers a1,a2,...,an,(1≤ai≤1018).

 

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.

 

 

 

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18;

const double Pi = acos(-1.0);

const int N = 2e3+, M = 1e6, mod = , inf = 2e9;

int p[N],H[N],cnt,A[][],mx,ini[N];

LL a[N];

void init() {

        for(int i = ; i <= ; ++i) {

            if(!H[i]) {

                p[cnt++] = i;

                for(int j = i+i; j <= ; j += i) {

                        H[j] = ;

                }

            }

        }

        ini[] = ;

        for(int i = ; i<= ; ++i) ini[i] = ini[i-]*%mod;

}

LL Guass(int n,int m) {

        int i, j;

        for(i = , j = ; i < n && j < m; ) {

            int x = -;

            for(int k = i; k < n; ++k) {

                if(A[k][j]) {

                    x = k;

                    break;

                }

            }

            if(x == -) {

                ++j;

                continue;

            }

            for(int k = ; k <= m; ++k) swap(A[i][k],A[x][k]);

            for(int u = i+; u < n; ++u) {

                if(A[u][j]) {

                    for(int k = ; k <= m; ++k) {

                        A[u][k] ^= A[i][k];

                    }

                }

            }

            ++i;

            ++j;

        }

        return m-i;

}

int main() {

        int T,cas = ,n;

        init();

        scanf("%d",&T);

        while(T--) {

            scanf("%d",&n);

            mx = ;

            for(int i = ; i < n; ++i) scanf("%I64d",&a[i]);

            memset(A,,sizeof(A));

            for(int i = ; i < n; ++i) {

                for(int j = ; j < cnt; ++j) {

                    while(a[i] % p[j] == ) {

                        A[j][i] ^= ;

                        a[i] /= p[j];

                        mx = max(mx,j+);

                    }

                }

            }

            printf("Case #%d:\n",cas++);

            cout<<ini[Guass(mx,n)] - <<endl;

        }

        return ;

}