Alex jest e-sportowcem.

W tych dniach Alex gra w grę strategiczną. Jego miasto można przedstawić jako prostokąt na płaszczyźnie kartezjańskiej, którego lewy dolny róg znajduje się w $(0,0)$, a prawy górny w $(n+1,n+1)$.

Alex zbudował $n$ wież obronnych, aby chronić miasto. Wieża $i$ znajduje się w punkcie $(x_i,y_i)$ i jest skierowana w stronę $d_i$. Wieże o różnych kierunkach chronią różne obszary, a mianowicie:

• Jeśli $d_i = 1$, wieża $i$ chroni obszar $\{(a,b) \mid a \ge x_i, b \ge y_i\}$;
• Jeśli $d_i = 2$, wieża $i$ chroni obszar $\{(a,b) \mid a \le x_i, b \ge y_i\}$;
• Jeśli $d_i = 3$, wieża $i$ chroni obszar $\{(a,b) \mid a \le x_i, b \le y_i\}$;
• Jeśli $d_i = 4$, wieża $i$ chroni obszar $\{(a,b) \mid a \ge x_i, b \le y_i\}$.

Jeśli Alex aktywuje $e$ wież, zużyje $e$ jednostek energii na godzinę. Chce on aktywować jak najmniejszą liczbę wież tak, aby każdy punkt $(x,y)$ w mieście ($x,y \in \mathbb{R}, 0 \le x,y \le n+1$) był chroniony. Czy potrafisz znaleźć optymalną strategię?

Wejście

Pierwsza linia wejścia zawiera liczbę zestawów danych $T$. Następnie następuje $T$ zestawów danych.

Dla każdego zestawu danych pierwsza linia zawiera liczbę całkowitą $n$, gdzie $n$ to liczba wież.

Kolejne $n$ linii zawiera po trzy liczby całkowite $x_i, y_i$ oraz $d_i$, oznaczające odpowiednio położenie i kierunek wieży $i$.

Wyjście

Dla każdego zestawu danych wypisz linię w formacie "$\texttt{Case #x: y}$", gdzie $\texttt{x}$ to numer zestawu danych (liczony od $1$), a $\texttt{y}$ to minimalna liczba wież. Jeśli ochrona całego miasta jest niemożliwa, wypisz "$\texttt{Impossible}$" (bez cudzysłowów).

Przykład

Przykład 1

2
3
1 1 1
2 2 2
3 3 3
4
1 1 1
2 2 3
2 1 2
1 2 4

Wyjście 1

Case #1: Impossible
Case #2: 4

Podzadania

Dla $10\%$ danych testowych spełnione jest $n \le 20,\ \sum n \le 100$.

Dla $30\%$ danych testowych spełnione jest $n \le 100,\ \sum n \le 500$.

Dla $40\%$ danych testowych spełnione jest $n \le 1000,\ \sum n \le 5000$.

Dla $70\%$ danych testowych spełnione jest $n \le 10^5,\ \sum n \le 5 \times 10^5$.

Dla wszystkich danych testowych spełnione jest $1 \le T \le 10^4,\ 1 \le n \le 10^6,\ \sum n \le 5 \times 10^6,\ 1 \le x_i,y_i \le n,\ 1 \le d_i \le 4$.

Ze względu na dużą ilość danych wejściowych, należy użyć szybkich metod wczytywania.