Given an array of $n$ positive integers, please find how many non-empty subarrays* satisfy the condition: the sum of the positive integers in the non-empty subarray is divisible by the maximum digit that appears in that non-empty subarray.

• An array $a$ is a non-empty subarray of an array $b$ if and only if $a$ can be obtained by deleting zero or more elements from the beginning of $b$ and zero or more elements from the end of $b$, and $a$ contains at least one element.

A digit refers to $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$ that make up a number. For example, the digits appearing in the array $[213]$ are $1, 2, 3$, and the maximum digit is $3$; the digits appearing in the array $[2025, 11, 15]$ are $0, 1, 2, 5$, and the maximum digit is $5$.

Input

Each test case contains multiple test data. The first line gives an integer $T$ ($1 \le T \le 10^4$), representing the number of test cases.

For each test case: The first line gives an integer $n$ ($1 \le n \le 10^5$), representing the length of the array. The second line gives $n$ positive integers $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^9$), representing the array.

It is guaranteed that the sum of $n$ over all test cases in each test point does not exceed $10^5$.

Output

For each test case, output a single integer on one line, representing the number of non-empty subarrays that satisfy the problem requirements.

Examples

Input 1

2
3
213 12 21
7
314 880 246 170 493 474 129

Output 1

4
7

Note

For the first test case in the example, there are 6 non-empty subarrays in total: For the non-empty subarray $[213]$, the sum of positive integers is $213$, the maximum digit appearing is $3$, $213$ is divisible by $3$, which satisfies the problem requirements. For the non-empty subarray $[12]$, the sum of positive integers is $12$, the maximum digit appearing is $2$, $12$ is divisible by $2$, which satisfies the problem requirements. For the non-empty subarray $[21]$, the sum of positive integers is $21$, the maximum digit appearing is $2$, $21$ is not divisible by $2$, which does not satisfy the problem requirements. For the non-empty subarray $[213, 12]$, the sum of positive integers is $213 + 12 = 225$, the maximum digit appearing is $3$, $225$ is divisible by $3$, which satisfies the problem requirements. For the non-empty subarray $[12, 21]$, the sum of positive integers is $12 + 21 = 33$, the maximum digit appearing is $2$, $33$ is not divisible by $2$, which does not satisfy the problem requirements. For the non-empty subarray $[213, 12, 21]$, the sum of positive integers is $213 + 12 + 21 = 246$, the maximum digit appearing is $3$, $246$ is divisible by $3$, which satisfies the problem requirements.

Therefore, the number of non-empty subarrays that satisfy the problem requirements is $4$.