给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \dots, A_N)$。

对于由整数 $L$ 和 $R$（满足 $1 \le L \le R \le N$）定义的连续子序列 $(A_L, A_{L+1}, \dots, A_R)$，如果满足以下条件，则称其为二次的：

• 存在实数 $a, b, c$，使得对于满足 $L \le i \le R$ 的每个整数 $i$，方程 $A_i = ai^2 + bi + c$ 均成立。

你的任务是将序列 $A$ 划分为若干个连续的二次子序列。在所有可能的划分方式中，输出所需子序列的最小数量。

你将被给定 $T$ 组测试用例。请输出每组测试用例的答案。

输入格式

输入按以下格式给出：

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

每个测试用例按以下格式给出：

$N$ $A_1 \ A_2 \ \dots \ A_N$

• 所有输入均为整数。
• $1 \le T \le 10^5$
• $1 \le N \le 2 \times 10^5$
• $-10^{18} \le A_i \le 10^{18}$
• 在单次输入的所有测试用例中， $N$ 的总和不超过 $2 \times 10^5$。

输出格式

输出 $T$ 行。 第 $i$ 行输出第 $i$ 组测试用例的答案。

样例

样例输入 1

4
12
-16 -9 -4 -1 0 0 0 0 1 4 9 16
8
2 0 2 5 0 3 0 8
1
0
5
1000000000000000000 250000000000000000 0 250000000000000000 1000000000000000000

样例输出 1

3
3
1
1

说明

在第一个样例中，给定的序列可以划分为三个二次子序列：$(-16, -9, -4, -1)$，$(0, 0, 0)$ 和 $(0, 1, 4, 9, 16)$。对于这些子序列，分别有 $(a, b, c) = (-1, 10, -25)$，$(0, 0, 0)$ 和 $(1, -16, 64)$ 满足条件。无法将该序列划分为少于 3 个二次子序列，因此答案为 3。

在第四个样例中，请注意输入值可能超过 32 位整数范围。