The GCD Partners - Repovive Starter Round 5 | Repovive

17G. The GCD Partners

3500 pts1.5s256 MB

You are given an array $a$ of $n$ positive integers.

A contiguous subarray $a[l \dots r]$ ( $1 \le l \le r \le n$ ) is called valid if for every index $i$ ( $l \le i \le r$ ), there exists at least one index $j$ ( $l \le j \le r$ , $i \neq j$ ) such that $\gcd(a_i, a_j) > 1$ .

Find the total number of valid contiguous subarrays of the array $a$ .

Input

The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) - the number of test cases.

The first line of each test case contains a single integer $n$ ( $1 \le n \le 3 \cdot 10^5$ ) - the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 3 \cdot 10^5$ ) - the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$ .

Output

For each test case, output a single integer — the total number of valid contiguous subarrays.

Samples

Input

Case 1

4
2 4 3 9

Case 2

5
2 4 6 8 10

Case 3

3
7 11 13

Case 4

4
1 2 4 1

Explanation

Case 1

The $3$ valid subarrays are:

Subarray $a[1 \dots 2]$ : $[2, 4]$ because $\gcd(2, 4) = 2 > 1$ .

Subarray $a[3 \dots 4]$ : $[3, 9]$ because $\gcd(3, 9) = 3 > 1$ .

Subarray $a[1 \dots 4]$ : $[2, 4, 3, 9]$ because $2$ pairs with $4$ , and $3$ pairs with $9$ .

Case 2

All elements are even, meaning any two elements share a common divisor of $2$ . Therefore, any subarray of length $\ge 2$ is valid. There are exactly $10$ such subarrays.

Output

Case 1

Case 2

Case 3

Case 4

You are given an array $a$ of $n$ positive integers.

Find the total number of valid contiguous subarrays of the array $a$ .

The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) - the number of test cases.

The first line of each test case contains a single integer $n$ ( $1 \le n \le 3 \cdot 10^5$ ) - the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 3 \cdot 10^5$ ) - the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$ .

The $3$ valid subarrays are:

Subarray $a[1 \dots 2]$ : $[2, 4]$ because $\gcd(2, 4) = 2 > 1$ .

Subarray $a[3 \dots 4]$ : $[3, 9]$ because $\gcd(3, 9) = 3 > 1$ .

Subarray $a[1 \dots 4]$ : $[2, 4, 3, 9]$ because $2$ pairs with $4$ , and $3$ pairs with $9$ .

All elements are even, meaning any two elements share a common divisor of $2$ . Therefore, any subarray of length $\ge 2$ is valid. There are exactly $10$ such subarrays.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

17G. The GCD Partners

Input

Output

Samples

17G. The GCD Partners

Input

Output

Samples