AT_utpc2024_q Quadratic Pieces

長さ $ 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 $ 個のテストケースが与えられるので、それぞれについて答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各ケースは以下の形式で与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 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 整数型に収まらない場合があることに注意してください。 ### Constraints - 入力は全て整数 - $ 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 $ 以下