この問題はサンプルです

注意

Sample 0 の注意事項を先にお読みください。

問題文

$N$ 個の小パスタが繋がってできた大パスタがあります．
左から $i \; \scriptsize (1 \leq i \leq N)$ 番目の小パスタの長さは $L_i$ です．

この大パスタを何回か折って，いくつかの中パスタ (小パスタがいくつか繋がったもの) に再び分割しようとしています．
ただし，見栄えのために，すべての中パスタの長さが等しくなるようにする必要があります．
このとき最大でいくつの中パスタへ分割することができますか？
求めてください．

大パスタは，それを構成する小パスタ同士の繋ぎ目でのみ折ることができます．

制約

• $1 \leq \Phi \leq 10^5$
• $1 \leq N$
• $\sum_{\phi} \Phi_{\phi}(N) \leq 10^5$
• $1 \leq L_i \leq 100 \; \scriptsize (1 \leq i \leq N)$

入力

各テストケースの入力は，それぞれ以下の形式で与えられる：

出力

答えを出力せよ．

サンプル

2
8
1 2 3 2 4 4 2 6
5
1 2 3 4 5

4
1

1. $1+2+3 = 2+4 = 4+2 = 6$ であるので，長さ $6$ の中パスタ $4$ つに分割することができます．(他に，たとえば長さ $8$ の中パスタ $3$ つに分割することもできますが，$4$ が最大です．)
2. 長さが $\sum L$ の中パスタ $1$ つに分割することができます．

• Sample 0
• Sample 2