AT_arc215_c [ARC215C] Strong Surname

異なる名字を持つ $ N $ 人の人がおり、 $ i $ 番目の人の名字はパラメータ $ (X_i,Y_i,Z_i) $ を持っています。異なる名字が同一のパラメータを持つこともあります。 今から $ N - 1 $ 回、以下のことが起こります。 - ある二人が親となり、その子供が一人出現する。親の二人は亡くなる。子供は、両親の名字のうち強い方を選んで自分の名字とする。パラメータ $ (x_1,y_1,z_1) $ を持つ名字がパラメータ $ (x_2,y_2,z_2) $ を持つ名字よりも強いとは、 $ x_1 > x_2 $ かつ $ y_1 > y_2 $ かつ $ z_1 > z_2 $ を満たすことである。親の名字に強弱が付けられないとき、子供は名字を両親の名字からランダムに選ぶ。 $ N $ 人のうち、その人の名字が最後の一人の名字となりうる人の数を求めて下さい。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ X_1 $ $ Y_1 $ $ Z_1 $ $ X_2 $ $ Y_2 $ $ Z_2 $ $ \vdots $ $ X_N $ $ Y_N $ $ Z_N $

$ T $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のテストケースについて、その人の名字が最後の一人の名字となりうる人の数を出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについては、例えば以下のようにイベントが起こることが考えられます。 $ i $ 番目の人の名字を名字 $ i $ と呼ぶことにする。 - 名字 $ 2 $ と名字 $ 4 $ の人が親になる。名字 $ 2 $ の方が強いため、子は名字 $ 2 $ を持つ。 - 名字 $ 2 $ と名字 $ 3 $ の人が親になる。名字 $ 3 $ の方が強いため、子は名字 $ 3 $ を持つ。 - 名字 $ 1 $ と名字 $ 3 $ の人が親になる。名字 $ 1 $ と名字 $ 3 $ では強弱が付けられないため、子は名字 $ 1 $ と $ 3 $ のいずれかを選ぶ。 名字 $ 2 $ や名字 $ 4 $ が最後の一人の名字になることはないため、答えは $ 2 $ になります。 ### Constraints - $ 1 \le T \le 2 \times 10^5 $ - $ 2 \le N \le 2 \times 10^5 $ - $ 1 \le X_i, Y_i, Z_i \le N $ - 全てのテストケースにおける $ N $ の総和は $ 2 \times 10^5 $ 以下 - 入力される値は全て整数