Link 有一个长度为 $n$ 的由正整数组成的序列 $a$。

Link 想知道该序列有多少个子数组的和为质数。也就是说，有多少对 $(l, r)$ ($1 \le l \le r \le n$) 满足 $\sum_{i=l}^r a_i$ 是质数。

输入格式

每个测试文件包含多个测试用例。第一行包含测试用例的数量 $T$ ($1 \le T \le 10^4$)。

接下来是每个测试用例的描述。

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示序列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$，$\sum a_i \le 10^6$)，表示序列的元素。

保证在一个测试文件中，所有测试用例的 $n$ 之和不超过 $10^6$，且所有测试用例的 $\sum a_i$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示和为质数的子数组数量。

样例

输入样例 1

2
4
1 2 3 4
12
1 1 4 5 1 4 1 9 1 9 8 10

输出样例 1

5
16

说明

在第一个样例中，合法的 $(l, r)$ 对为：

• $l = 1, r = 2$：该子数组的和为 $3$。
• $l = 2, r = 2$：该子数组的和为 $2$。
• $l = 2, r = 3$：该子数组的和为 $5$。
• $l = 3, r = 3$：该子数组的和为 $3$。
• $l = 3, r = 4$：该子数组的和为 $7$。