Sample 1 - Pasta Normalization Problem

この問題はサンプルです

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

個の小パスタが繋がってできた大パスタがあります．
左から 番目の小パスタの長さは です．

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

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

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

答えを出力せよ．

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

4
1

1. であるので，長さ の中パスタ つに分割することができます．(他に，たとえば長さ の中パスタ つに分割することもできますが， が最大です．)
2. 長さが の中パスタ つに分割することができます．

• Sample 0
• Sample 2