Alexはeスポーツ選手です。

最近、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$ 基の防御塔を起動すると、1時間あたり $e$ 単位のエネルギーを消費します。城内のあらゆる点 $(x,y)$ ($x,y \in \mathbb{R}, 0 \le x,y \le n+1$) が守られるようにしつつ、起動する防御塔の数を最小化したいと考えています。最適な戦略を見つけることができますか？

入力

入力の最初の行にはテストケースの数 $T$ が与えられ、続いて $T$ 個のテストケースが続きます。

各テストケースにおいて、最初の行には防御塔の数 $n$ が含まれます。

続く $n$ 行には、それぞれ防御塔 $i$ の位置と向きを表す3つの整数 $x_i, y_i, d_i$ が含まれます。

出力

各テストケースについて、"$\texttt{Case #x: y}$" という形式で1行に出力してください。ここで $\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$ を満たします。

本問題は入力量が大きいため、高速な読み込み方法を使用してください。