E. Maximums and Minimumstime limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou 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 minimum and maximum numbers are found among a_l, a_{l+1}, \ldots, a_r.  The check is passed if the maximum number is divisible by the minimum number. InputThe 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.OutputFor each test case, print a single integer — the number of pairs of indices that pass the check.ExampleInput
61122 422 342 4 7 14716 5 18 7 7 12 14616 14 2 6 16 2Output
1
3
2
7
10
19
NoteBelow 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:   (1, 1): the maximum is 2, the minimum is 2, 2 \mid 2, so the check is passed.  (1, 2): the maximum is 4, the minimum is 2, 2 \mid 4, so the check is passed.  (2, 2): the maximum is 4, the minimum is 4, 4 \mid 4, so the check is passed. In the third test case, there are 3 segments:   (1, 1): the maximum is 2, the minimum is 2, 2 \mid 2, 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, 3 \mid 3, so the check is passed. 
61122 422 342 4 7 14716 5 18 7 7 12 14616 14 2 6 16 2
1 3 2 7 10 19 
['combinatorics', 'data structures', 'divide and conquer', 'number theory', '*2700']