In 2020, due to $i s s u e s$ worldwide, $C u p i d o n u s$ moved his tutoring program online. For a small reasonable amount (4000 - 5000 Euros) he can teach you the ways of the $c u p i d$, so you will be able to become a $C u p i d o n$. Of course inferior to $C u p i d o n u s$.
As a result $N$ smarties registered for his program. Since $C u p i d o n u s$ is really busy, he decided to organize a test in order to select the right candidate in one go. As a result, he aligned all the smarties on the $O Y$ axis and asked each of them to shoot an arrow in the semiplane with $x > 0$. $C u p i d o n u s$ will select the maximum number of smarties such that any two trajectories of their arrows do $N O T$ intersect.
$C u p i d o n u s$ asked you to supervise the test and tell him how many candidates will be selected.
The first line of the input will contain the number of test cases $T$ ($1 <= T <= 100000$).
The first line of each test case will be the number $N$ ($1 <= N <= 10^5$), the number of smarties who registered to become a $C u p i d o n$.
The following $N$ lines of each test case will each contain $3$ integers $a_i$, $x_i$, $y_i$ ($-2^(52) <= a_i, y_i <= 2^(52)$, $1 <= x_i <= 2^(52)$, $1 <= i <= N$), the position of the $i$th smartie on the $O Y$ axis and the coordinates where his arrow landed. All $a_i$ are pairwise distinct.
It is guaranteed that the sum of $N$ over all test cases does not exceed $500000$.
The output should contain $T$ lines, each containing the answer to the corresponding test case.
For the first example we can choose the smarties with indexes: 2, 3, 5. See image below.
## Input
The first line of the input will contain the number of test cases $T$ ($1 <= T <= 100000$).The first line of each test case will be the number $N$ ($1 <= N <= 10^5$), the number of smarties who registered to become a $C u p i d o n$.The following $N$ lines of each test case will each contain $3$ integers $a_i$, $x_i$, $y_i$ ($-2^(52) <= a_i, y_i <= 2^(52)$, $1 <= x_i <= 2^(52)$, $1 <= i <= N$), the position of the $i$th smartie on the $O Y$ axis and the coordinates where his arrow landed. All $a_i$ are pairwise distinct.It is guaranteed that the sum of $N$ over all test cases does not exceed $500000$.
## Output
The output should contain $T$ lines, each containing the answer to the corresponding test case.
[samples]
## Note
For the first example we can choose the smarties with indexes: 2, 3, 5. See image below.
**Definitions**
Let $ G = (V, E) $ be an undirected, unweighted, connected graph with $ |V| = n $, $ |E| = m $, and no self-loops or parallel edges.
Each edge $ e_i = (u_i, v_i) \in E $ is labeled with a character $ c_i \in \Sigma $, where $ \Sigma $ is the set of lowercase Latin letters.
**Constraints**
1. $ 2 \leq n \leq 200000 $
2. $ 1 \leq m \leq 200000 $
3. For all $ e_i = (u_i, v_i, c_i) $, $ 1 \leq u_i, v_i \leq n $, $ u_i \ne v_i $, $ c_i \in \text{a-z} $
**Objective**
Find a path $ P = (v_0, v_1, \dots, v_k) $ from $ v_0 = 1 $ to $ v_k = n $ such that:
- $ k $ is minimized (shortest path),
- Among all shortest paths, the string $ s = c_1 c_2 \dots c_k $, where $ c_j $ is the label on edge $ (v_{j-1}, v_j) $, is lexicographically minimal.
Output:
- The length $ k $ of the path,
- The sequence of vertices $ v_0, v_1, \dots, v_k $,
- The string $ s $ of edge labels along the path.