题目描述

题目背景

幽冥的庭院里，无尽的樱花缓缓飘落，时间在这里仿佛也放慢了脚步。魂魄妖梦手握比她人还高的扫帚，正以惊人的专注力清扫着白玉般的小径。她的目标是：在下一阵裹挟着更多花瓣的春（冥界之风）吹来之前，将眼前这一段路清理得一尘不染。这不仅是一项工作，更是她身为庭师的修行。

西行寺幽幽子大人则慵懒地靠在廊柱旁，如云的粉色长发几乎与身后的樱花树融为一体。她指尖捻着一片刚刚接住的花瓣，那双总是半阖的眸子里映着纷繁的落英，轻声哼唱着无人知晓年代的古老歌谣。当她看到妖梦额角渗出细汗，却依旧一丝不苟时，一股温柔的恶作剧心思悄然浮现。

她微笑着，对着妖梦刚刚扫净的那片空地，轻轻地、调皮地吹了一口气。一阵微风卷起，廊下堆积的几片花瓣像被赋予了生命，翩翩起舞，精准地重新散落在那片空地上。

妖梦的动作顿住了。她看着那几片“不合时宜”的花瓣，肩膀微微垮下一点，嘴巴抿成一条线，显然是有些困扰，却绝不敢对幽幽子大人有半分抱怨。她只是深吸一口气，再次举起扫帚，准备从头来过。

“呵呵呵……”幽幽子优雅的笑声飘了过来，“妖梦认真的样子，也是这庭院里最好的风景之一呢。”妖梦的脸微微一红，扫地的动作似乎更快、也更用力了。

题目描述

妖梦所在的庭院可以看作一个平面直角坐标系中的电子迷宫。这个电子迷宫中有 \(n\) 个位于第一象限的弹幕发射器，第 \(i\) 个弹幕发射器位于点 \(\left(x_i, y_i\right)\)，且它会向上、下、左、右中的某一个方向发射激光。我们称一个点在一个弹幕发射器的照明路径上，当且仅当该点在以弹幕发射器为原点，向其照射方向画出的射线上（注意：弹幕发射器本身也在自己的照明路径上）。由于激光的功率很大，相互照射时会引发危险，因此，不会有任意两个弹幕发射器同时在对方的照明路径上。

为防止光污染，妖梦决定在电子迷宫中放置一些障碍物（可以放在弹幕发射器所在的位置），以防止激光照射到无穷远处。现在，妖梦想知道，至少需要放置多少个障碍物，才能使所有的弹幕发射器的照射路径上都至少有一个障碍物。

输入格式

输入的第一行包含一个整数 \(t\) （\(1 \le t \le 100\)），表示测试用例的数量。

接下来是 \(t\) 个测试用例的描述。

每个测试用例的第一行包含一个整数 \(n\) （\(1 \le n \le 300\)），表示弹幕发射器的数量。

接下来 \(n\) 行，第 \(i\) 行包含三个整数 \(x_i\)， \(y_i\) 和 \(d_i\) （\(1 \le x_i, y_i \le 10^9\)， \(d_i\in \{0, 1, 2, 3\}\)），表示第 \(i\) 个弹幕发射器的坐标是 \(\left(x_i, y_i\right)\)，同时：

• 若 \(d_i = 0\)，则表示该弹幕发射器向上发射激光；
• 若 \(d_i = 1\)，则表示该弹幕发射器向右发射激光；
• 若 \(d_i = 2\)，则表示该弹幕发射器向下发射激光；
• 若 \(d_i = 3\)，则表示该弹幕发射器向左发射激光。

保证所有测试用例中 \(n\) 的总和不超过 \(3000\)。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示妖梦最少需要放置的障碍物的数量。

样例输入

2
6
5 5 0
3 7 1
9 9 2
9 1 3
5 2 0
1 20 3
1
1 1 0

样例输出

3
1

提示

在样例测试用例 1 中，一种方案是分别在坐标 \(\left(5, 7\right)\) （覆盖第 \(1\) 束、第 \(2\) 束以及第 \(5\) 束激光）， \(\left(9, 1\right)\) （覆盖第 \(3\) 束以及第 \(4\) 束激光）以及 \(\left(-2025, 20\right)\) （覆盖第 \(6\) 束激光）处各放置一个障碍物。可以证明，不存在更优的方案。