問題文

長さ N の整数列 A = (A_1, A_2, \dots, A_N) が与えられます。

1 \le L \le R \le N を満たす整数 L, R によって定まる連続部分列 (A_L, A_{L + 1}, \dots, A_R) が以下の条件を満たすとき、その連続部分列は 2 次関数的であると定めます。

• ある実数 a, b, c が存在し、L \le i \le R を満たす任意の整数 i が A_i = a i^2 + b i + c を満たす。

整数列 A をいくつかの 2 次関数的な連続部分列に分割することを考えます。分割後の連続部分列の個数としてありうる値のうち最小値を出力してください。

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 入力は全て整数
• 1 \le T \le 10^5
• 1 \le N \le 2 \times 10^5
• -10^{18} \le A_i \le 10^{18}
• 1 つの入力に含まれるテストケースについて、N の総和は 2 \times 10^5 以下

入力例 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 -500000000000000000 -1000000000000000000 -500000000000000000 1000000000000000000

出力例 1

3
3
1
1

1 つ目のテストケースについて、与えられた整数列は 3 つの 2 次関数的な連続部分列 (-16, -9, -4, -1), \,(0, 0, 0),\, (0, 1, 4, 9, 16) に分割できます。 実際、それぞれの連続部分列について、(a, b, c) = (-1, 10, -25), \, (0, 0, 0),\, (1, -16, 64) が条件を満たしていることがわかります。 2 つ以下の 2 次関数的な連続部分列に分割することはできないので、答えは 3 となります。

4 つ目のテストケースについて、入力値が 32 bit 整数型に収まらない場合があることに注意してください。