小 Petya 开始学习如何书写数字，他刚刚学会了书写以下 5 个数字：

他绘制每个数字时，其尺寸与上图完全相同，但他可能会进行以下零个或多个更新：

• 缩放数字的宽度，保持宽度为整数单位。
• 缩放数字的高度，保持高度为整数单位。
• 将数字顺时针旋转 90、180 或 270 度。

注意，缩放数字不会改变线段的粗细，并且会均匀地影响整个数字。例如，在旋转前将数字 3 在垂直方向上进行缩放，会始终保持中间的水平线段恰好位于其他水平线段的中间。

现在，他在一个无限的二维平面上书写了许多数字，并遵循以下规则：

• 数字之间不会相互接触或重叠（即一个数字的线段不会与另一个数字的线段接触）。
• 所有垂直线段都将放置在具有整数 $X$ 坐标的垂直线上。
• 所有水平线段都将放置在具有整数 $Y$ 坐标的水平线上。
• 所有端点都位于具有整数坐标的点上（端点是指垂直或水平线段的末端）。

Petya 通过绘制线段来绘制数字，每条线段的起点和终点坐标均为整数，且所有线段保证为垂直或水平，长度为正整数。注意，线段可以接触甚至重叠，但当这种情况发生时，这些线段属于同一个数字（请检查第二个样例测试用例）。

下图展示了一些永远不会出现在输入中的无效数字：

其中 1 旋转不正确，3 的中间水平线段长度错误，2 的中间水平线段不再位于中间，4 是镜像的（未旋转）。

你将获得一份 Petya 绘制的线段列表，并保证这些线段将仅构成上述的有效数字。你的任务是找出每个数字被绘制了多少次。

• 第一个样例测试用例代表第一张图片。
• 第二个样例测试用例代表下图（注意某些线段可能会重叠和/或接触以形成更长的线段）：

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量（$1 \le T \le 100$）。接下来是 $T$ 个测试用例。

每个测试用例以一行包含一个整数 $N$ 开始，表示要绘制的线段数量（$1 \le N \le 100,000$）。接下来有 $N$ 行，每行包含 4 个整数 $X_1, Y_1, X_2$ 和 $Y_2$，表示点 $(X_1, Y_1)$ 和 $(X_2, Y_2)$ 之间的线段（$1 \le X_1, Y_1, X_2, Y_2 \le 1,000,000,000$）。

输出格式

对于每个测试用例，打印 5 个由空格分隔的整数，每个整数表示每个数字被绘制的次数，顺序与第一张图从左到右的顺序相同。

样例

输入 1

2
17
1 1 1 7
1 7 4 7
4 7 4 1
4 1 1 1
6 1 6 7
11 1 8 1
8 1 8 4
8 4 11 4
11 4 11 7
11 7 8 7
13 1 16 1
16 1 16 7
16 7 13 7
16 4 13 4
21 1 21 7
21 4 18 4
18 4 18 7
24
1 2 1 4
1 4 1 8
1 6 1 10
1 11 4 11
2 1 2 9
2 1 3 1
2 5 3 5
2 9 3 9
4 7 4 8
4 8 5 8
5 8 5 7
5 7 4 7
5 2 5 6
5 4 8 4
8 4 8 2
5 9 5 10
5 10 6 10
6 10 6 9
6 9 7 9
7 9 7 10
8 7 8 10
8 10 9 10
9 10 9 7
9 7 8 7

输出 1

1 1 1 1 1
2 2 1 1 1