Alex is an e-sports player.

These days, Alex is playing a war strategy game. His city can be viewed as a rectangle on the Cartesian plane with its bottom-left corner at $(0,0)$ and its top-right corner at $(n+1, n+1)$.

Alex has built $n$ defensive towers to protect the city. Defensive tower $i$ is located at $(x_i, y_i)$ and has a direction $d_i$. Towers with different directions protect different regions, specifically:

• If $d_i = 1$, tower $i$ protects the region $\{(a,b) \mid a \ge x_i, b \ge y_i\}$;
• If $d_i = 2$, tower $i$ protects the region $\{(a,b) \mid a \le x_i, b \ge y_i\}$;
• If $d_i = 3$, tower $i$ protects the region $\{(a,b) \mid a \le x_i, b \le y_i\}$;
• If $d_i = 4$, tower $i$ protects the region $\{(a,b) \mid a \ge x_i, b \le y_i\}$.

If Alex activates $e$ towers, he will consume $e$ units of energy per hour. He wants to activate the minimum number of towers such that any point $(x,y)$ in the city $(x,y \in \mathbb{R}, 0 \le x,y \le n+1)$ is protected. Can you find the optimal strategy?

Input

The first line of the input gives the number of test cases $T$, followed by $T$ test cases.

For each test case, the first line contains an integer $n$, where $n$ is the number of defensive towers.

The next $n$ lines each contain three integers $x_i, y_i$, and $d_i$, representing the position and direction of tower $i$.

Output

For each test case, output a single line containing "$\texttt{Case #x: y}$", where $\texttt{x}$ is the test case number (starting from 1) and $\texttt{y}$ is the minimum number of towers. If it is impossible to protect the entire city, output "$\texttt{Impossible}$" (without quotes).

Examples

Input 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

Output 1

Case #1: Impossible
Case #2: 4

Subtasks

For $10\%$ of the test data, $n \le 20,\ \sum n \le 100$.

For $30\%$ of the test data, $n \le 100,\ \sum n \le 500$.

For $40\%$ of the test data, $n \le 1000,\ \sum n \le 5000$.

For $70\%$ of the test data, $n \le 10^5,\ \sum n \le 5 \times 10^5$.

For all test data, $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$.

Due to the large volume of input, please use fast I/O methods.