“线段是连接两点间的最短路径”——这句格言是字节帝国（Byteantean Empire）道路设计师的主要动力。因此，帝国境内修建的所有道路都是笔直的，且贯穿整个国家。字节人在每两条道路的交叉点处都建立了一座城镇。为了避免歧义，字节人从不让超过两条道路在同一点相交。

字节帝国的皇帝现在想把他的国家划分为两个省，并尽可能使两个省内的城镇数量相等。帝国中的某一条道路将成为两个省之间的边界。严格位于边界上的城镇不归任何一个省管辖，而仅由皇帝本人直接管辖。因此，他希望计算出对于每一条道路，位于该道路一侧的城镇数量与位于另一侧的城镇数量之差的绝对值。

宫廷制图师 Byteman 花了许多天试图完成皇帝的命令。你的任务是编写一个程序来帮助他完成这项工作。

输入格式

标准输入的第一行包含一个整数 $n$ ($1 \le n \le 1\,000$)，表示帝国中道路的数量。接下来的 $n$ 行，每行包含一条道路的描述——四个整数 $x_1, y_1, x_2, y_2$ ($-1\,000 \le x_1, y_1, x_2, y_2 \le 1\,000$，点 $(x_1, y_1)$ 与 $(x_2, y_2)$ 不重合)，由空格分隔。每一组四元数代表一条经过点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的直线。没有两条道路重合。没有三条道路交于同一点。我们假设帝国足够大，所有代表道路的直线的交点都位于其边界之内。

输出格式

你的程序应向标准输出写入 $n$ 行，即输入中所有道路的答案（顺序与输入顺序相同）。对于每一条道路，答案是位于该道路两侧的城镇数量之差的绝对值。

样例

输入 1

4
1 -1 1 10
0 0 1 0
2 0 2 1
4 4 -1 -1

输出 1

1
2
3
2

说明 1

示例中有五个城镇，坐标分别为 (0, 0), (1, 0), (1, 1), (2, 0) 和 (2, 2)。