Ramazan has decided to go into serious business — growing cabbage.

The field for growing cabbage is an infinite grid. Each cell of the field can contain one head of cabbage.

Ramazan has planted only a part of the field. He planned to use several rectangular plots of the field, and it turned out that some of them might overlap. A cell of the field belongs to the plantings if it lies in at least one of the rectangles.

Formally, Ramazan chose $n$ rectangular plots $(x_i^L, y_i^L, x_i^R, y_i^R)$ ($x_i^L \le x_i^R, y_i^L \le y_i^R, 1 \le i \le n$). A cell $(x, y)$ contains cabbage if there exists at least one chosen rectangle $i$ ($1 \le i \le n$) such that $x_i^L \le x \le x_i^R$ and $y_i^L \le y \le y_i^R$.

In the past, Ramazan was a programmer (and a winner), so he decided to use AI-powered robots for periodic maintenance of the plantings. One robot can service an arbitrary horizontal segment of cells $(x_1^{\text{robot}}, x_2^{\text{robot}}, y^{\text{robot}})$, that is, all cells $(x, y)$ such that $x_1^{\text{robot}} \le x \le x_2^{\text{robot}}$ and $y = y^{\text{robot}}$.

It is important that the robots travel only on plots with plantings. He realized that to minimize the number of robots, it is important to use horizontal segments that cannot be extended.

Ramazan will use a robot on the segment of cells $(x_1^{\text{robot}}, x_2^{\text{robot}}, y^{\text{robot}})$ if: All cells $(x, y)$ such that $x_1^{\text{robot}} \le x \le x_2^{\text{robot}}$ and $y = y^{\text{robot}}$ belong to the plantings; The cell $(x_1^{\text{robot}} - 1, y^{\text{robot}})$ does not belong to the plantings; * The cell $(x_2^{\text{robot}} + 1, y^{\text{robot}})$ does not belong to the plantings.

Your task is to collect important statistics about the robots that will work on the plantation. We say that a pair $(x_1, x_2)$ is serviced in row $y$ if there exists a robot working exactly on the segment $(x_1, x_2, y)$.

• Find all pairs $(x_1, x_2)$ that are serviced in some row.
• For each such pair $(x_1, x_2)$, find the number of rows in which it is serviced.
• For each such pair $(x_1, x_2)$, find the maximum number of consecutive rows in which it is serviced. In other words, find the maximum number $k$ such that there exists a segment of $k$ consecutive rows $[y_1, y_2]$ ($y_2 - y_1 + 1 = k$) such that for any row $y_1 \le y \le y_2$, the pair $(x_1, x_2)$ is serviced in row $y$.

Input

Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 200\,000$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 200\,000$) — the number of chosen rectangular plots.

In the next $n$ lines, four integers $x_i^L, y_i^L, x_i^R, y_i^R$ are given ($1 \le x_i^L \le x_i^R \le 10^9, 1 \le y_i^L \le y_i^R \le 10^9$) — the descriptions of the chosen rectangular plots.

Let $N$ be the sum of $n$ over all test cases in one test. It is guaranteed that $N \le 200\,000$.

Output

For each test case, first output a single integer $p$ ($p \ge 1$) — the number of pairs $(x_1, x_2)$ that are serviced in some row.

In the next $p$ lines, output four integers $x_1, x_2, cnt, k$ ($1 \le x_1 \le x_2 \le 10^9, 0 \le cnt, k \le 10^9$). The number $cnt$ must be equal to the number of rows in which the pair $(x_1, x_2)$ is serviced. The number $k$ must be equal to the maximum number of consecutive rows in which the pair $(x_1, x_2)$ is serviced.

All pairs $(x_1, x_2)$ must be distinct. Each pair that is serviced in some row must be output exactly once. You may output the pairs in any order.

Subtasks

For a test case, let $w$ be the width of the field, i.e., $w = \max_{i=1}^n x_i^R$, and $h$ be the height of the field, i.e., $h = \max_{i=1}^n y_i^R$.

• If for a test your solution incorrectly finds the set of pairs $(x_1, x_2)$ that are serviced in some row, the solution receives the verdict "Wrong Answer".
• If in all tests of a subtask and required subtasks the solution:
  • correctly finds the set, but not all $cnt$ are correct, it receives 50% of the points for the subtask.
  • correctly finds the set and all $cnt$, but not all $k$ are correct, it receives 75% of the points for the subtask.
  • correctly finds the set, all $cnt$, and all $k$, it receives 100% of the points for the subtask.

Note that to receive partial points for a subtask, it is still necessary to output some values for $cnt$ and $k$ for each pair $(x_1, x_2)$, but they do not necessarily have to be correct.

Examples

Input 1

4
2
2 2 3 3
3 3 4 4
2
2 1 2 3
1 2 3 2
4
2 2 4 5
3 4 9 7
2 9 9 10
7 1 9 7
7
2 1 2 9
5 1 6 8
4 5 7 6
1 8 4 10
1 6 3 6
1 2 7 3
4 1 7 1

Output 1

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

Note

In the first test case, robots are used on segments $(2, 3, 2), (2, 4, 3), (3, 4, 4)$. Thus, the pairs $(2, 3), (2, 4), (3, 4)$ are serviced in some row, and each of them is serviced in exactly one row.

In the second test case, robots are used on segments $(2, 2, 1), (2, 4, 2), (2, 2, 3)$. Thus, the pairs $(2, 2), (2, 4)$ are serviced in some row. The pair $(2, 2)$ is serviced in rows 1 and 3, and the pair $(2, 4)$ is serviced in row 2.

Explanations of examples

First and second test cases

Third and fourth test cases

In the first test case, robots are used on segments $(2, 3, 2), (2, 4, 3), (3, 4, 4)$. Thus, the pairs $(2, 3), (2, 4), (3, 4)$ are serviced in some row, and each of them is serviced in exactly one row.

In the second test case, robots are used on segments $(2, 2, 1), (2, 4, 2), (2, 2, 3)$. Thus, the pairs $(2, 2), (2, 4)$ are serviced in some row. The pair $(2, 2)$ is serviced in rows 1 and 3, and the pair $(2, 4)$ is serviced in row 2.