메탈

당신은 금속 공예가로서 강철 세공품을 만들려고 합니다. 먼저 커다란 강판 위에 점 $n$개를 표시하고, 그 $n$개의 점을 잇는 다각형을 강판에서 잘라냅니다. 절단은 강판 위쪽에 걸쳐 놓은 긴 수평 막대에 매달린 레이저 두 개로 다각형의 경계를 따라 강판을 녹여서 수행합니다(그림 1 참고). 막대는 수직, 즉 $y$축과 평행하며, 멈추지 않고 오직 $x$축의 양의 방향(강판의 왼쪽에서 오른쪽)으로만 연속해서 움직입니다. 각 레이저는 막대 위에서만 움직일 수 있고, 두 레이저는 막대 위에서 서로 만날 수 없습니다. 또한 막대는 왼쪽에서 오른쪽으로 단조롭게 진행하며, 현재 위치보다 왼쪽으로는 결코 되돌아갈 수 없습니다.

이 조건들 때문에 만들 수 있는 다각형은 항상 단순하면서 단조롭습니다. 다각형 $P$가 단순하다는 것은, 서로 이웃한 두 변이 공유하는 끝점에서만 만나는 경우를 제외하고 어떤 두 변도 교차하지 않으며 $P$ 내부에 구멍이 없다는 뜻입니다. 다각형 $P$가 단조롭다는 것은, $P$와 임의의 수직선의 교집합이 공집합이거나, 한 점이거나, 하나의 선분이라는 뜻입니다.

그림 1. 수직 막대에 매달린 두 레이저로 이루어진 절단 도구.

세공품의 좋은 모양을 고르기 위해, 당신은 주어진 $n$개의 점으로 만들 수 있는 서로 다른 단순 단조 다각형이 몇 개인지 알고 싶습니다. 당신의 과제는 그 개수를 구하는 것입니다. 예를 들어 그림 2는 서로 다른 단순 단조 다각형이 정확히 4개 존재하는 일곱 점의 예시를 보여 줍니다.

그림 2. 일곱 개의 점에 대한 서로 다른 네 개의 단순 단조 다각형.

입력은 표준 입력으로 주어집니다. 첫째 줄에는 테스트 케이스의 수 $T$가 주어집니다. 각 테스트 케이스의 첫째 줄에는 점 집합 $S = \{s_0, s_1, \ldots, s_{n-1}\}$의 점 개수를 나타내는 정수 $n$ ($3 \le n \le 50$)이 주어집니다. 이어지는 $n$개의 줄에는 각각 음이 아닌 두 정수 $x_i$와 $y_i$ ($0 \le x_i, y_i \le 200000$)가 주어지며, 이는 점 $s_i$의 좌표가 $(x_i, y_i)$임을 뜻합니다. $S$의 어떤 두 점도 같은 $x$좌표를 갖지 않습니다.

각 테스트 케이스마다, $S$의 $n$개의 점을 잇는 서로 다른 단순 단조 다각형의 개수를 한 줄에 하나씩 표준 출력으로 출력합니다.