H. Prime Segments
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Link has a sequence of length $$$n$$$ consisting of positive integers $$$a$$$.

Link wants to know how many subarrays of this sequence have a sum that is a prime number. In other words, how many pairs $$$(l,r)$$$ ($$$1 \leq l \leq r \leq n$$$) satisfy $$$\sum_{i=l}^{r} a_i$$$ being a prime number.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 10^4$$$). The description of the test cases follows.

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$), the length of the sequence.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$, $$$\sum a_i \leq 10^6$$$), representing the elements of the sequence.

It is guaranteed that the sum of all $$$n$$$ across the test cases in a single file does not exceed $$$10^6$$$, and the sum of all $$$\sum a_i$$$ across the test cases in a single file does not exceed $$$10^6$$$.

Output

For each test case, output a single line containing one integer — the number of subarrays whose sum is a prime number.

Example
Input
2
4
1 2 3 4
12
1 1 4 5 1 4 1 9 1 9 8 10
Output
5
16
Note

In the first sample test case, the valid $$$(l,r)$$$ pairs are:

  • $$$l=1, r=2$$$: the sum of this subarray is $$$3$$$.
  • $$$l=2, r=2$$$: the sum of this subarray is $$$2$$$.
  • $$$l=2, r=3$$$: the sum of this subarray is $$$5$$$.
  • $$$l=3, r=3$$$: the sum of this subarray is $$$3$$$.
  • $$$l=3, r=4$$$: the sum of this subarray is $$$7$$$.