Ineq

정수 쌍의 집합 $S = \{(x_1, y_1), \ldots, (x_n, y_n)\}$가 주어진다. 모든 $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 = \{(a_1, b_1, c_1), \ldots, (a_m, b_m, c_m)\}$가 존재하는지 판별하라.

첫째 줄에 테스트 케이스의 수를 나타내는 정수 $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, 0, 1), (0, 1, 1), (-1, 0, 1), (0, -1, 1)\}$이다.