Сізге ұзындығы \(n\) болатын \(a_1, a_2, \ldots, a_n\) массиві беріледі.

Сіздің міндетіңіз – массивті \(a\) келесі шарттар орындалатындай етіп минималды санды жалпақ үздіксіз сегменттерге (бөлімдерге) бөлу:

1. Массив кем дегенде екі бөлімге бөлінуі тиіс.

2. Әрбір элемент тек бір ғана бөлімге тиесілі болуы керек.

3. Әрбір бөлімдегі элементтер қосындысы бірдей болуы керек.

Осы шарттар орындалатын бөлімдер санының ең аз санын табыңыз, немесе олай бөлу мүмкін емес екенің анықтаңыз.

Енгізу

Әр тесті бірнеше сынақтардан тұрады.

Бірінші жолда бір бүтін сан \(t\) (\(1 \le t \le 10^5\)) беріледі — сынақтардың саны.
Әр сынақтың сипаттамасы келесідей:

Бірінші жолда бүтін сан \(n\) (\(2 \le n \le 10^6\)) беріледі — массивтің ұзындығы.

Екінші жолда \(n\) бүтін сан \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^{12}\)) беріледі — массивтің элементтері.

Барлық сынақтардағы \(n\) сандарының қосындысы \(10^6\)-ды аспайды.

Шығару

Әр сынақ үшін бір бүтін санды шығарыңыз: Шарттар орындалатын минималды сегмент саны. Егер мұндай бөліну мүмкін болмаса, \(-1\) шығарыңыз.

Мысалдар

Енгізу 1

7
2
1 1
3
1 2 3
5
1 5 2 3 4
4
1 4 2 5
4
3 3 1 2
6
3 1 4 1 5 2
9
3 1 4 1 5 9 2 6 5

Жауап 1

2
2
-1
-1
3
2
-1

Ескертпелер

Екінші кіріс деректер жиынтығында \([1, 2]\) және \([3]\) үзінділеріне бөлуге болады.

Дәлелдеуге болады, үшінші кіріс деректер жиынтығында бөлініс жоқ.