暂无测试数据。

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}\)