Алекс — киберспортсмен.

В эти дни Алекс играет в военную стратегическую игру. Его город можно представить как прямоугольник на декартовой плоскости с левым нижним углом в $(0,0)$ и правым верхним углом в $(n+1,n+1)$.

Алекс построил $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\}$.

Если Алекс активирует $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$.

В связи с большим объемом входных данных, пожалуйста, используйте быстрые методы ввода.