Range Convex Checker

Problem Description

定义一个二维平面上的点集 $S$ 是好的，当且仅当 $S$ 中所有点都在 $S$ 的凸包边界上。特别地，若 $|S|=1$ 或 $S$ 中所有点共线，我们也认为 $S$ 是好的。 给定平面上 $n$ 个 两两不同 的点 $P_1,P_2,\cdots,P_n$，求有多少个区间 $[l,r]$ 满足 $1\le l\le r\le n$ 且 $S_{l,r}=\{P_l,P_{l+1},\cdots,P_r\}$ 是好的。

Input

第一行输入一个正整数 $T$（$1\le T\le 12517$），代表数据组数。 对于每组数据，第一行输入一个整数 $n$（$1\le n\le 3\cdot 10^5$），接下来 $n$ 行每行输入两个整数 $x_i,y_i$（$|x_i|,|y_i|\le 10^7$），代表 $P_i$ 的坐标为 ($x_i,y_i$)。 保证 $\sum n\le 10^6$。

Output

对于每组数据，输出一行一个整数，代表满足条件的区间数。

Sample Input

3
6
-1 -1
-1 1
2 -1
2 2
1 0
3 1
6
-2 -4
0 -5
-2 -2
-4 -2
0 -2
3 5
7
-4 4
-1 5
1 5
7 1
2 5
5 6
-5 -3

Sample Output

17
19
22

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（10）