Codeforces Round 823 (Div. 2) |
---|
Finished |
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 \le l \le r \le n$$$, that pass the check. The check is performed in the following manner:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 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 \le n \le 5 \cdot 10^5$$$) — the size of the array.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.
For each test case, print a single integer — the number of pairs of indices that pass the check.
61122 422 342 4 7 14716 5 18 7 7 12 14616 14 2 6 16 2
1 3 2 7 10 19
Below $$$x \mid y$$$ 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$$$, $$$1 \mid 1$$$, so the check is passed, and the answer is $$$1$$$.
In the second test case, there are $$$3$$$ segments:
In the third test case, there are $$$3$$$ segments:
Name |
---|