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