This is the hard version of the problem. The difference between the versions is that in this version, you are asked to find the sum of $f(b)$ over all contiguous subsequences $b$ of $a$. You can hack only if you solved all versions of this problem.

For some sequence $b$ of $k$ positive integers, the cost of the sequence is defined as follows$^{\text{∗}}$:

$$\mathtt{cost}(b)=\left\lceil{\frac{b_k}{\min(b_1,b_2,\ldots,b_k)}}\right\rceil$$

Assume that you partition a sequence $c$ into one or more sequences, so that the sequences become $c$ when concatenated. For example, when the sequence $c$ is $[3,1,4,1,5]$, a few valid ways to partition the sequence are $[[3,1],[4,1,5]]$, $[[3],[1,4,1],[5]]$, $[[3,1,4,1,5]]$. On the other hand, $[[3,1],[1,5]]$ and $[[3,4,1],[1,5]]$ are not valid ways to partition the sequence.

For a partition of a sequence $c$ of positive integers, the total cost of the partition is defined as the sum of the costs of each sequence in the partition. Then, let us define $f(c)$ as the minimum total cost to partition the sequence $c$.

Given a sequence $a$ of $n$ positive integers, you must compute the following:

$$\sum_{l=1}^{n} {\sum_{r=l}^{n} f([a_l,a_{l+1},\ldots,a_r])}$$

$^{\text{∗}}$Given a real value $x$, $\left\lceil{x}\right\rceil$ is defined as the smallest integer no less than $x$. For example, the value of $\left\lceil{3.14}\right\rceil$ is $4$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 4 \cdot 10^5$).

The second line of each test case contains $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^{18}$).

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

Output

For each test case, output the answer to the problem on a separate line.

Note

For the first test case, the following are all contiguous subsequences of $a$ and their corresponding values:

• $[3] \to [[3]]$: $f([3])=1$;
• $[3,1] \to [[3,1]]$: $f([3,1])=1$;
• $[3,1,4] \to [[3,1],[4]]$: $f([3,1,4])=2$;
• $[3,1,4,1] \to [[3,1,4,1]]$: $f([3,1,4,1])=1$;
• $[3,1,4,1,5] \to [[3,1,4,1],[5]]$: $f([3,1,4,1,5])=2$;
• $[1] \to [[1]]$: $f([1])=1$;
• $[1,4] \to [[1],[4]]$: $f([1,4])=2$;
• $[1,4,1] \to [[1,4,1]]$: $f([1,4,1])=1$;
• $[1,4,1,5] \to [[1,4,1],[5]]$: $f([1,4,1,5])=2$;
• $[4] \to [[4]]$: $f([4])=1$;
• $[4,1] \to [[4,1]]$: $f([4,1])=1$;
• $[4,1,5] \to [[4,1],[5]]$: $f([4,1,5])=2$;
• $[1] \to [[1]]$: $f([1])=1$;
• $[1,5] \to [[1],[5]]$: $f([1,5])=2$;
• $[5] \to [[5]]$: $f([5])=1$.

Therefore, the answer for the first test case is $1+1+2+1+2+1+2+1+2+1+1+2+1+2+1=21$.