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\)