Problem Description

This class is on art. Mr. Picasso gives every baby a piece of white drawing paper and let them paint on it.

Baby Volcano is going to color the drawing paper black. For convenience, the drawing paper can be regarded as a Cartesian coordinate system, and initially, all points on it is white.

Baby Volcano plans to paint the drawing paper in $n$ steps. In the $i$th step, he will color rectangular $R_i$ black, where the lower left corner of $R_i$ is $(l_i,0)$, the upper right corner of $R_i$ is $(r_i,h_i)$.

Let $P_i$ be the drawing paper after the first $i$ steps, your task is to calculate the perimeter of black area on $P_i$.

Input

The first line contains a single integer $t(1 \leq t \leq 100)$, the number of testcases.

For each testcase, the first line contains a single integer $n(1 \leq n \leq 2 \times 10^5)$, the number of steps.

Then $n$ lines follow. Each line contains $3$ integers $l_i,r_i,h_i (1 \leq l_i, < r_i \leq 10^9, 1 \leq h_i \leq 10^9)$.

The input guarantees that there are no more than $3$ testcases with $n > 1000$.

Output

For each testcase, output $n$ lines. Each line contains a single integer, representing the perimeter of black area after the first $i$ steps.

1
6
1 2 2
3 4 3
5 6 2
1 4 1
2 6 1
3 7 4

6
14
20
20
20
22