write a go solution for Description:
You are given an array a_1,a_2,ldots,a_n of positive integers.

Find the number of pairs of indices (l,r), where 1<=l<=r<=n, that pass the check. The check is performed in the following manner:

1. The minimum and maximum numbers are found among a_l,a_l+1,ldots,a_r.
2. The check is passed if the maximum number is divisible by the minimum number.

Input Format:
The first line contains a single integer t (1<=t<=10) — the number of test cases. Then the test cases follow.

Each test case consists of two lines.

The first line contains a single integer n (1<=n<=5*10^5) — the size of the array.

The second line contains n integers a_1,a_2,...,a_n (1<=a_i<=10^6).

It is guaranteed that the sum of n over all test cases does not exceed 5*10^5.

Output Format:
For each test case, print a single integer — the number of pairs of indices that pass the check.

Note:
Below xmidy denotes that y is divisible by x.

In the first test case, there is one pair (1,1), the maximum for this pair is 1, the minimum is also 1, 1mid1, so the check is passed, and the answer is 1.

In the second test case, there are 3 segments:

- (1,1): the maximum is 2, the minimum is 2, 2mid2, so the check is passed.
- (1,2): the maximum is 4, the minimum is 2, 2mid4, so the check is passed.
- (2,2): the maximum is 4, the minimum is 4, 4mid4, so the check is passed.

In the third test case, there are 3 segments:

- (1,1): the maximum is 2, the minimum is 2, 2mid2, so the check is passed.
- (1,2): the maximum is 3, the minimum is 2, 3 isn't divisible by 2, so the check is failed.
- (2,2): the maximum is 3, the minimum is 3, 3mid3, so the check is passed.. Output only the code with no comments, explanation, or additional text.