An $$$n \times n$$$ matrix $$$B$$$ is called an interval matrix if for each row $$$i$$$, there exists a contiguous range of columns $$$[l_i, r_i]$$$ ($$$1 \le l_i \le r_i \le n$$$) filled with ones, while all other elements in the row are zero. Formally, $$$B_{i, j} = 1$$$ if $$$l_i \le j \le r_i$$$, and $$$B_{i, j} = 0$$$ otherwise.

You are given an integer $$$n$$$ and an initial interval matrix $$$A$$$, described by $$$n$$$ triples $$$(l_i, r_i, a_i)$$$. The $$$i$$$-th row of $$$A$$$ corresponds to the interval $$$[l_i, r_i]$$$, and $$$a_i$$$ is the cost associated with modifying this row.

Let $$$\mathcal{S}$$$ be the set of all possible $$$n \times n$$$ interval matrices. We define $$$X$$$ as the maximum possible determinant among them: $$$$$$ X = \max\limits_{B \in \mathcal{S}} \operatorname{det}(B). $$$$$$ (Note that $$$|\mathcal{S}| = \left(\frac{n(n + 1)}{2}\right)^n$$$, as each row can be any valid interval)

Your goal is to transform $$$A$$$ into a matrix $$$A'$$$ such that $$$\operatorname{det}(A') = X$$$. To achieve this, you can perform the following operation any number of times:

Choose a row index $$$i$$$ ($$$1 \le i \le n$$$) and a new valid interval $$$[L, R]$$$ ($$$1 \le L \le R \le n$$$).
Replace the current interval of the $$$i$$$-th row with $$$[L, R]$$$.
The cost of this operation is $$$a_i$$$.

Find the minimum total cost required to make the determinant of the matrix equal to $$$X$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5 \cdot 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 10^6$$$) — the size of the matrix.

The next $$$n$$$ lines describe the rows of the matrix $$$A$$$. The $$$i$$$-th of these lines contains three integers $$$l_i$$$, $$$r_i$$$, and $$$a_i$$$ ($$$1 \le l_i \le r_i \le n$$$, $$$1 \le a_i \le 10^9$$$) — the interval boundaries and the cost of modifying the $$$i$$$-th row.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer — the minimum total cost required to make $$$\operatorname{det}(A) = X$$$.

Note

In the first example, $$$n = 2$$$ and it can be shown that $$$X = 1$$$. The matrix is $$$A = \begin{bmatrix} 1 & 0\\0 & 1\end{bmatrix}$$$. Since $$$\operatorname{det}(A) = 1$$$, no operations are needed.

In the second example, $$$X$$$ is still $$$1$$$, but the matrix is $$$A = \begin{bmatrix} 0 & 1\\1 & 0\end{bmatrix}$$$. The determinant is $$$-1$$$, so we must transform the matrix.

It can be proven that it is impossible to reach a determinant of $$$1$$$ with a single operation. Therefore, we must modify both rows. One possible sequence of operations is:

$$$$$$ \begin{bmatrix} 0 & 1\\1 & 0\end{bmatrix} \xrightarrow{i = 2, \, L = 2, \, R = 2} \begin{bmatrix} 0 & 1\\0 & 1\end{bmatrix} \xrightarrow{i = 1, \, L = 1, \, R = 2} \begin{bmatrix} 1 & 1\\0 & 1\end{bmatrix} $$$$$$

The final matrix has a determinant of $$$1$$$. The total cost is $$$a_2 + a_1 = 1 + 1 = 2$$$, which is the answer.

Maximize Determinant

Examples