hwf 是一个非常喜欢吃披萨的人。某天，天上掉下了一张披萨，被 hwf 和高老师看到了。

高老师把披萨分成了 $n$ 份, 第 $i$ 份的角度为 $a_i$。为了公平起见，他们决定由 hwf 把 $n$ 份披萨分成两堆，然后高老师肯定会挑一堆角度和多的，hwf 拿剩下的一堆。hwf 想吃到尽可能多的披萨，但是 hwf 的心思已经全在吃披萨上了。

快帮助 hwf，告诉他最多能吃到多少披萨吧！

第一行为一个整数 $t\ (1\le t\le 500)$，表示数据的组数。接下来对于每组数据：
第一行有一个整数 $n\ (2\le n\le 360)$，表示披萨被分成的份数。
第二行有 $n$ 个整数 $a_1,a_2,\ldots,a_n\ (1\le a_i\lt 360)$，分别表示第 $i$ 份披萨的角度。

保证 $\sum_{i=1}^n a_i=360$

对于每组数据，输出一行：
第一行为一个整数，表示hwf最多可以吃到披萨的角度数。