问题背景

$\dfrac 1 4$ 遇到了一道水题，叒完全不会做，于是去请教小 D。小 D 都没看就切掉了这题，嘲讽了 $\dfrac 1 4$ 一番就离开了。

于是，$\dfrac 1 4$ 只好来问你，这道题是这样的：

问题描述

给定一个长度为 n 的正整数序列 $\{a_i\}$。

将 $\{1, 2, \cdots, n\}$ 划分成两个非空集合 $S,T$，使得 $\gcd(\prod\limits_{i\in S}a_i,\prod\limits_{i\in T}a_i)=1$。

求划分方案数，对 $10^9 +7$ 取模。

输入格式

第一行，一个非负整数 $t$，代表数据组数。

每组数据的第一行，一个正整数 $n$。

第二行，$n$ 个正整数，代表 {ai}。

输出格式

输出 $t$ 行，每行一个非负整数，代表答案对 $10^9 +7$ 取模的结果。

样例

Input

3
3
2 3 1
3
2 3 6
4
2 3 6 1

Output

6
0
2

Explanation

• 第 1 组数据，任意一种非空集合划分均满足。
• 第 2 组数据，任意一种非空集合划分均不满足。
• 第 3 组数据，$S = \{1, 2, 3\}, T = \{4\}, \gcd(a_1 a_2 a_3, a_4) = 1$，或者 $S = \{4\}, T = \{1, 2, 3\}, \gcd(a_4, a_1 a_2 a_3) = 1$。

子任务

保证，$0 ≤ t ≤ 5，1 ≤ n ≤ 105，1 ≤ ai ≤ 106$。

时限 1s，空限 512M

来源

2018 国庆雅礼 NOIP 培训。一切权利归原作者所有。侵权删除。