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$$$.

Inverse Minimum Partition (Hard Version)

Examples