#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/17/problems/G

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

The GCD Partners - Repovive Starter Round 5 | Repovive | 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.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

17G. The GCD Partners

Input

Output

Samples

17G. The GCD Partners

Input

Output

Samples