AlgoLiga 2018

Franek, który pracując jako listonosz z wielkim zaangażowaniem dostarcza przesyłki, swój czas wolny poświęca na (jakże szlachetne) hobby, jakim jest czytanie książek. Ponieważ zaczął gromadzić książki już w dzieciństwie, ma teraz w domu całkiem sporą biblioteczkę. Gdy z biegiem lat książek przybywało, na półce, na której wszystkie się znajdują, robił się coraz większy bałagan, ponieważ Franek nie dbał o to, by przeczytaną książkę odkładać na właściwe miejsce.

Teraz nadszedł czas na wielkie porządki. Franek opracował w tym celu następującą metodę. Dla każdej z książek na półce bierze pod uwagę trzy cechy: liczbę stron, wysokość i (co najwyżej sześcioliterowy) skrót tytułu. Chciałby teraz uporządkować książki przede wszystkim według jednego z tych parametrów. Jeśli wiele książek ma taką samą wartość tego pierwszego parametru, to decydować powinien drugi. Oczywiście, jeśli ten również jest taki sam, należy wziąć pod uwagę trzeci parametr. Dla Franka nie ma znaczenia, jaką wagę będą miały poszczególne cechy. Nie jest też dla niego ważne, czy książki będą uporządkowane według rosnącej czy malejącej wartości poszczególnych parametrów. Jeden z możliwych efektów porządkowania może więc być taki: Książki ułożone są od najwyższej do najniższej. Jeśli kilka książek ma taką samą wysokość, to są ułożone od tej o najmniejszej liczbie stron do tej o największej. Jeśli wiele książek ma taką samą wysokość i liczbę stron, to są ułożone według leksykograficznego porządku skrótów tytułów.

I tu dochodzimy do sedna sprawy. Franek chce doprowadzić książki do stanu uporządkowania jak najszybciej, tzn. w jak najmniejszej liczbie ruchów. Ruch polega na przełożeniu dowolnej książki z miejsca, w którym się znajduje w dowolne inne miejsce, tj. na początek półki albo na jej koniec, albo pomiędzy dwie inne książki.

Napisz program, który wyznaczy, w jakiej najmniejszej liczbie ruchów można uporządkować książki.

Wejście

W pierwszej linii liczba przypadków testowych t (1 ≤ t ≤ 10).

Każdy z testów rozpoczyna liczba całkowita n (1 ≤ n ≤ 300000), oznaczająca liczbę książek.
W kolejnych n liniach trzy cechy każdej z książek:
liczba stron g (1 ≤ g ≤ 10⁹), wysokość h (1 ≤ h ≤ 10⁹) i skrót tytułu jako ciąg wielkich liter angielskiego alfabetu o długości od 1 do 6 znaków.

Liczba książek z wszystkich testów razem nie przekracza 300000.

Wyjście

Dla każdego przypadku testowego, w osobnej linii jedna liczba całkowita oznaczająca minimalną liczbę ruchów, prowadzących do uporządkowania książek.

Przykład

Wejście:
2
3
10 15 AA
20 13 A
15 10 C
6
90 15 OGNIEM
70 25 PIRX
90 20 POTTER
90 18 POTTER
70 15 OGNIEM
70 18 PIRX

Wyjście:
0
1

Wyjaśnienie do przykładu: Książki w pierwszym zestawie są już uporządkowane malejąco według wysokości. W drugim zestawie wystarczy przełożyć drugą książkę na przedostatnią pozycję i będą wtedy ułożone według następującego klucza: malejąco według liczby stron, rosnąco według skrótu tytułu, malejąco według wysokości.