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.