AT_awtf2025_c Get Closer

$ 1 $ 以上 $ N $ 以下の整数が書かれたボールがあります． 具体的には，整数 $ i $ ( $ 1 \leq i \leq N $ ) の書かれたボールが $ A_i $ 個あります． $ S=A_1+A_2+\cdots+A_N $ と定義します． ここで， $ S $ が正の偶数であることが保証されます． $ S $ 個のボールを $ S/2 $ 個のペアに分けます． ペアになった $ 2 $ つのボールに書かれた整数は異なる必要があります． なお，この問題の制約下でこのようなペア分けが可能であることが証明できます． 各ペアについて，以下の操作を行います． - $ 2 $ つのボールに書かれた整数がそれぞれ $ x,y $ ( $ x < y $ ) であるとする． これらのボールに書かれている数を，それぞれ $ x+0.5,y-0.5 $ で置き換える． すべてのペアについて操作を終えたあと，同じ数が書かれているボールの個数の最大値を $ d $ とおきます． $ d $ としてありうる最小値を求めてください． $ 1 $ つの入力につき， $ T $ 個のテストケースを解いてください．

入力は以下の形式で標準入力から与えられる． > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

各テストケースに対し，答えを出力せよ．

### Sample Explanation 1 $ 1 $ つ目のテストケースについて考えます． 整数 $ x,y $ の書かれたボールのペアを $ (x,y) $ で表すことにします． 例えば， $ (1,3),(2,3),(2,4) $ とペア分けすると，操作後にボール書かれている数は $ 1.5,2.5,2.5,2.5,2.5,3.5 $ になります． 同じ数が書かれているボールの個数の最大値は $ d=4 $ です． 一方， $ (1,2),(2,3),(3,4) $ とペア分けすると，操作後にボール書かれている数は $ 1.5,1.5,2.5,2.5,3.5,3.5 $ になります． 同じ数が書かれているボールの個数の最大値は $ d=2 $ となります． $ d $ を $ 2 $ より小さくすることはできないので， $ 2 $ が答えになります． ### Constraints - $ 1 \leq T \leq 125000 $ - $ 2 \leq N \leq 250000 $ - $ 0 \leq A_i \leq 10^9 $ - $ S=A_1+A_2+\cdots+A_N $ は正の偶数である - $ A_i \leq S/2 $ - $ 1 $ つの入力における $ N $ の総和は $ 250000 $ を超えない - 入力はすべて整数