Alex 是一位電競選手。

這些天，Alex 正在玩一款戰爭策略遊戲。他的城池可以被看作笛卡兒平面上的一個矩形，其左下角為 $(0,0)$，右上角為 $(n+1,n+1)$。

Alex 建造了 $n$ 座防禦塔來保衛城池。防禦塔 $i$ 位於 $(x_i,y_i)$，方向為 $d_i$。方向不同的防禦塔能夠保護不同的區域，具體來說：

• 若 $d_i = 1$，防禦塔 $i$ 能保護區域 $\{(a,b) \mid a \ge x_i, b \ge y_i\}$；
• 若 $d_i = 2$，防禦塔 $i$ 能保護區域 $\{(a,b) \mid a \le x_i, b \ge y_i\}$；
• 若 $d_i = 3$，防禦塔 $i$ 能保護區域 $\{(a,b) \mid a \le x_i, b \le y_i\}$；
• 若 $d_i = 4$，防禦塔 $i$ 能保護區域 $\{(a,b) \mid a \ge x_i, b \le y_i\}$。

如果 Alex 啟用了 $e$ 座防禦塔，他每小時將會消耗 $e$ 的單位能量。他想要啟用盡量少數量的防禦塔，使得城池中的任何點 $(x,y)(x,y \in \mathbb{R}, 0 \le x,y \le n+1)$ 都能被保護。你能找到最優策略嗎？

輸入格式

輸入的第一行給出了測試點組數 $T$，接下來是 $T$ 組測試點。

對於每組測試點，第一行包含一個整數 $n$，其中 $n$ 是防禦塔的數量。

接下來的 $n$ 行，每行包含三個整數 $x_i,y_i$ 和 $d_i$，表示防禦塔 $i$ 的位置和方向。

輸出格式

對於每組測試點，輸出一行包含 "$\texttt{Case #x: y}$"，其中 $\texttt{x}$ 是測試點編號（從 $1$ 開始），以及 $\texttt{y}$ 是最少數量的防禦塔。如果不可能保護整座城池，輸出 "$\texttt{Impossible}$"（不包括引號）。

範例

範例 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

範例 1 輸出

Case #1: Impossible
Case #2: 4

子任務

對於 $10\%$ 的測試資料，滿足 $n \le 20,\ \sum n \le 100$。

對於 $30\%$ 的測試資料，滿足 $n \le 100,\ \sum n \le 500$。

對於 $40\%$ 的測試資料，滿足 $n \le 1000,\ \sum n \le 5000$。

對於 $70\%$ 的測試資料，滿足 $n \le 10^5,\ \sum n \le 5 \times 10^5$。

對於全部測試資料，滿足 $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$。

由於本題輸入量較大，請使用較快的讀入方式。