The 21st Hunan Provincial Collegiate Programming Contest——2025-湖南省赛-H. Prime Segments · znzryb
## 题目大意
**题目描述**
给定一个长度为 $n$ 的正整数序列 $a$。
求该序列中有多少个连续子段的和为素数。换言之，计算满足 $1 \le l \le r \le n$ 且 $\sum_{i=l}^r a_i$ 为素数的数对 $(l, r)$ 的数量。
**输入格式**
第一行包含一个整数 $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$。
**输出格式**
对于每个测试用例，输出一行一个整数，表示和为素数的子段数量。
**样例**
**输入：**
```
2
4
1 2 3 4
12
1 1 4 5 1 4 1 9 1 9 8 10
```
**输出：**
```
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$。
## 思路讲解
## AC代码
::: 源代码
```cpp
```
:::
## 心路历程（WA，TLE，MLE……）