#451 LIS and query 2

Statement

Statement language

A subsequence of a sequence $B$ of length $N$ is a sequence obtained by removing zero or more elements from $B$ . The order of the remaining elements must be the same as in $B$ .

A subsequence is nondecreasing if every element is greater than or equal to the preceding element. Let $f(B)$ be the length of a longest nondecreasing subsequence of $B$ .

You are given a sequence $A=[A_1,A_2,\cdots,A_N]$ of length . For , define

A[x:y]=[A_x,A_{x+1},\cdots,A_y].

You are also given $Q$ queries. For each query $(l,r)$ , compute

\sum_{x=l}^{r}\sum_{y=x}^{r} f(A[x:y]).

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print $Q$ lines. The $j$ -th line must contain the answer to the $j$ -th query.

Constraints

$1 \leq T \leq 20$ .
$1 \leq N \leq 1\,000\,000$ .
$1 \leq Q \leq$ .

Subtasks

#	Score	Constraints
1	11	$N,Q \leq 200$ in each test case. The sum of $N$ over all test cases does not exceed $200$ . The sum of $Q$ over all test cases does not exceed .

Samples

Input

Output

The first query of the first test case contains six contiguous subarrays. Their values of $f$ are $1,1,2,1,2,1$ , whose sum is $8$ .

The sequence in the second test case is nondecreasing. For its first query, the sum of the lengths of all contiguous subarrays is .