시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

Given a set of integer pairs S = {(x1, y1), . . . ,(xn, yn)}, determine if a set of integer triples T = {(a1, b1, c1), . . . ,(am, bm, cm)} exists such that aixj + biyj < ci for all i and j, and there doesn’t exist an integer pair (x', y') not belonging to S such that aix' + biy' < ci for all i.

입력

The first line contains a single integer t (1 ≤ t ≤ 105), denoting the number of test cases.

Each test case is described with an integer n (1 ≤ n ≤ 105), followed by n lines containing two integers xi and yi each (−109 ≤ xi, yi ≤ 109). All pairs (xi, yi) within one test case are distinct.

The sum of n over all test cases does not exceed 105.

출력

For each test case, display a separate line with 1 if the answer is positive, and 0 otherwise.

예제 입력 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

힌트

In the first test case, one possible set of triples is {(1, 0, 1),(0, 1, 1),(−1, 0, 1),(0, −1, 1)}.