该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师有一个正整数数组，他想找到一个分割位置，使得分割点左边所有元素的和等于右边所有元素的和。

具体来说，如果存在一个位置$p$（将前$p$个元素作为左半部分，剩余元素作为右半部分），使得左边和等于右边和，则输出$p$。如果有多个满足条件的位置，输出最小的$p$；如果不存在，输出$-1$。

例如数组$[1, 2, 3, 4, 5, 15]$总和为$30$，在$p=5$处分隔时，左边$1+2+3+4+5=15$，右边$15=15$，满足条件，输出$5$。

Format

Input

第一行一个正整数$T(1 \leq T \leq 10)$，表示测试组数。

对于每组测试，第一行一个正整数$n(1 \leq n \leq 10^5)$。

第二行$n$个正整数$a_i(1 \leq a_i \leq 10^4)$。

Output

对于每组数据，输出一行一个整数，表示满足条件的最小分割位置$p$（即左边有$p$个元素），如果不存在则输出$-1$。

Samples

2
6
1 2 3 4 5 15
4
1 2 3 3

5
-1

Limitation

1s, 1024KiB for each test case.