给定一个整数对集合 $S = \{(x_1, y_1), \dots, (x_n, y_n)\}$，判断是否存在一个整数三元组集合 $T = \{(a_1, b_1, c_1), \dots, (a_m, b_m, c_m)\}$，使得对于所有的 $i$ 和 $j$，满足 $a_i x_j + b_i y_j < c_i$，且不存在任何不属于 $S$ 的整数对 $(x', y')$ 满足对于所有的 $i$，都有 $a_i x' + b_i y' < c_i$。

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。

每个测试用例包含一个整数 $n$ ($1 \le n \le 10^5$)，随后有 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($-10^9 \le x_i, y_i \le 10^9$)。同一测试用例中的所有对 $(x_i, y_i)$ 均不相同。

所有测试用例的 $n$ 之和不超过 $10^5$。

对于每个测试用例，如果答案为肯定，则输出 1，否则输出 0。

样例

输入格式 1

4
1
0 0
5
2 1
0 0
1 1
1 0
2 2
3
1 3
5 1
4 2
3
1 3
6 1
4 2

输出格式 1

1
1
0
1

说明

在第一个测试用例中，一个可能的三元组集合是 $\{(1, 0, 1), (0, 1, 1), (-1, 0, 1), (0, -1, 1)\}$。