Alice is the biggest seller in the town who sells notebooks. She has $N$ customers to satisfy. Each customer has three parameters $L_i$, $R_i$, and $Z_i$ denoting the arrival time, departure time, and quantity of notebooks required.

Each customer has to be supplied a total of $Z_i$ notebooks between $L_i$ and $R_i$ inclusive. What is the minimum rate of $W$ notebooks per unit time by which if Alice produces so that it satisfies the demand of each customer?

Note that Alice does not need to supply $Z_i$ to customer $i$ for per unit time but the total of $Z_i$ between $L_i$ and $R_i$ and distribution does not need to be uniform.

Input format

• The first line contains $T$ denoting the number of test cases.
• The first line of each test case contains an integer $N$.
• Next $N$ lines of each test case contains three space-seperated integers $L_i$, $R_i$, and $Z_i$ as described in the problem statement,

Output format

For each test case, print a single line containing the minimum rate of production $W$.

Constraints

$1 \leq T \leq 1000$

$1 \leq N \leq 200000$

$1 \leq L[i],R[i],Z[i] \leq 200000 \forall i \in [1,N]$

$L[i] \leq R[i] \forall i \in [1,N]$

$\sum_{i=1}^{T} N \leq 200000$