题目描述

谢谢大家上次为我们的蛇年吉祥物Snaky解决了年货的问题！！

但是ta现在又有了问题，因为最近亲戚来访，Snaky已经得知了会有11个孩子明天来拜年，现在ta打算购买一些糖果作为给11个孩子的礼物。但是上次的糖果都已经被吃完了（孩子们最喜欢吃糖果了），于是ta想再买一些糖果，同时ta想要ta的巢穴中的糖果数量是11的倍数（因为有11个孩子，ta可不想偏心），不过ta的数学很差（Snaky怎么会数学呢），所以ta邀请你陪同ta一同到超市购买糖果，但是有一个问题，商店内的糖果都是按袋买的，必须一次性买一袋，不能零散地买，每一袋糖果的数量是固定的，Snaky最喜欢ta的孩子了，所以他要在满足公平的情况下，买最多的糖果。简单来说就是：

• 初始条件下Snaky没有糖果
• 最终糖果数必须是11的倍数
• 商店内的糖果会以数组表示，每包糖果只能买一次，不能重复购买，即数组中的数不能重复选取
• 要求买到的糖果数量尽可能多

输入格式

输入包含多个测试用例

第一行输入一个整数 t (1 ≤ t ≤ 10)，表示测试用例的个数

对每个测试用例：

输入一个整数 n (1 ≤ n ≤ 100000)，表示超市可以购买的糖果袋的总数 另换一行输入 n 个整数，表示每一袋糖果所含的糖果个数num (1 ≤ num ≤ 1000)

输出格式

对每个测试用例：

输出可以买到最多的糖果数

示例

input

5
8
5 2 5 2 5 9 10 10
3
6 9 1
3
5 5 9
3
2 1 8
8
10 3 6 4 10 1 9 4

output

44
0
0
11
44

解释

这里对第一个测试样例进行解释，可以选取5 5 5 9 10 10, 可得结果为44

限制

时间限制： 1s 空间限制： 128MB