暂无测试数据。

Background

本题是一道模板题

Description

已知$p_1, p_2, \cdots, p_n$为素数。求方程
$$a^2 + b^2 = \prod_{i=1}^n{p_i}$$
的整数解的数量

Format

Input

输入的第一行包含一个整数$T$
接下来有$T$组数据。
每组数据第一行包含一个整数$n$
接下来有$n$个素数$p_i$

Output

输出$T$个整数，表示各组数据解的数量。

Sample 1

Input

1
1
5

Output

8

Details

当$p=5$时，有8组解，分别为：
$$(1,2), (-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1)$$

Limitation

本题分为三部分：弱化数据（25%）、标准数据（25%）和全面数据（50%）
对于弱化数据，你可以暴力解决。
对于标准数据，你可以经过找规律解决，即使你的结论并不强力。
对于全面数据，你要严格分析出所有的条件。每个条件有一部分的分数。

弱化数据：5.0s的时限和512 MB的内存

对于50%的数据，$T = 1$, $n = 1$, $p \leqslant 10^5$
对于100%的数据，$T \leqslant 5$, $n \leqslant 3$, $p \leqslant 10^{5}$

标准数据：5.0s的时限和512 MB的内存

对于25%的数据，$T \leqslant 10^5,$n = 2$,$p \leqslant 10^{7}\(
另有25%的数据，\)T = 1$,$n \leqslant 10$,$p \leqslant 10^{7}\(
另有25%的数据，\)T \leqslant 10^5$,$n \leqslant 30$,$p \leqslant 7\(
对于100%的数据，\)T \leqslant 10^5$,$n \leqslant 30$,$p \leqslant 10^{7}$

全面数据：5.0s的时限和512 MB的内存

对于25%的数据，$T \leqslant 10^8$, $n \leqslant 30$, $p \leqslant 10^{7}$
另有25%的数据，$T \leqslant 10^5$, $n \leqslant 10^5$, $p \leqslant 10^{5}$
另有25%的数据，$T \leqslant 10^5$, $n \leqslant 30$, $p \leqslant 10^{1,000}$
另有25%的数据，$T \leqslant 10^7$, $n \leqslant 10^4$, $p \leqslant 10^{100}$