题目背景
「据说，踏上光桥的条件是收集到同时满足这些限制的所有钥匙。」
「这里有前人所留下的一组钥匙，但解读出限制条件还需要些许时日，所以目前无法验证其真伪。」
你的任务是初步判断这组钥匙是否真实且完整，换言之，是否有一组可能的限制，使得面前的所有钥匙即为这组限制的答案。
题目描述
给出一个整数对集
$$ S = \{ (x_1, y_1) \ldots (x_n, y_n) \} $$
询问是否存在一个整数三元组集
$$ T = \{ (a_1, b_1, c_1) \ldots (a_m, b_m, c_m) \} $$
使得对于所有 $1 \leq i \leq m, 1 \leq j \leq n$，有
$$ a_i x_j + b_i y_j < c_i $$
且不存在一个整数对 $(x', y') \not\in S$，使得对于所有 $1 \leq i \leq m$，满足
$$ a_i x' + b_i y' < c_i $$
输入格式
本题有多组测试数据。
第一行包含一个正整数 $T$，表示测试数据组数。
接下来依次描述 $T$ 组测试数据。
对于每组测试数据，第一行包含一个正整数 $n$，表示已知整数对集 $S$ 的大小。
接下来 $n$ 行，第 $i$ 行包含两个整数 $x_i, y_i$，描述第 $i$ 个整数对 $(x_i, y_i)$。保证所有整数对 $(x_i, y_i)$ 各不相同。
输出格式
对于每组测试数据输出一行，如果存在满足条件的整数三元组集 $T$ 则输出 $1$，否则输出 $0$。
样例 1 输入
4
1
0 0
2
1 1
3 3
3
0 0
2 3
3 4
4
1 2
2 1
4 5
3 7样例 1 输出
1
0
1
0样例 2
见下发文件中的 key/key2.in 与 key/key2.ans，该样例满足 Subtask 5 的要求。
样例 3
见下发文件中的 key/key3.in 与 key/key3.ans，该样例满足 Subtask 6 的要求。
样例 4
见下发文件中的 key/key4.in 与 key/key4.ans。
数据范围
令 $\sum n$ 表示测试点内所有测试数据的 $n$ 之和。
对于所有数据，保证 $1 \leq T \leq 10^6, 1 \leq \sum n \leq 10^6, -10^9 \leq x_i, y_i \leq 10^9$。
| 子任务 | $\sum n \leq$ | $x_i, -x_i, y_i, -y_i \leq$ | 特殊性质 | 子任务依赖 | 分值 |
|---|---|---|---|---|---|
| $1$ | $1 $ | $10^3$ | 无 | 无 | $3$ |
| $2$ | $2 $ | $10^3$ | 无 | $1$ | $3$ |
| $3$ | $3 $ | $10^3$ | 无 | $1 \sim 2$ | $4$ |
| $4$ | $10^6$ | $10^9$ | $\rm A$ | 无 | $10$ |
| $5$ | $10^6$ | $10^9$ | $\rm B$ | 无 | $10$ |
| $6$ | $10^6$ | $10^9$ | $\rm C$ | 无 | $10$ |
| $7$ | $10^3$ | $10^3$ | 无 | $1 \sim 3$ | $10$ |
| $8$ | $10^3$ | $10^9$ | 无 | $1 \sim 3, 7$ | $10$ |
| $9$ | $10^6$ | $10^3$ | 无 | $1 \sim 3, 7$ | $10$ |
| $10$ | $10^6$ | $10^9$ | 无 | $1 \sim 9$ | $30$ |
特殊性质 $\rm A$：保证 $x_i, y_i$ 在 $[-10^9, 10^9]$ 内随机生成。
特殊性质 $\rm B$： 对于所有 $1 \leq i \leq n$，保证 $\dfrac{x_i}{y_i}$ 相同。
特殊性质 $\rm C$：令 $x_I = \min x_i, x_A = \max x_i, y_I = \min y_i, y_A = \max y_i$，保证 $(x_I, y_I), (x_I, y_A), (x_A, y_I), (x_A, y_A) \in S$。