G. Super Subarray
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In this problem, subarray is defined as non-empty sequence of consecutive elements.

We define a subarray as Super Subarray if the summation of all elements in the subarray is divisible by each element in it.

Given an array a of size n, print the number of Super Subarrays in a.

Input

The first line of the input contains a single integer T (1 ≤ T ≤ 100), the number of test cases.

The first line of each test case contains one integer n (1 ≤ n ≤ 2000), the length of array a.

The second line of each test case contains the sequence of elements of the array a1, a2, ..., an (1 ≤ ai ≤ 109), ai is the i-th element of the array a.

Output

For each test case, print a single integer that represents the number of Super Subarrays in a, on a single line.

Example
Input
2
5
1 2 3 4 5
5
2 3 4 3 6
Output
6
6