题目内容

塔塔君最喜欢到塔塔村的塔塔炸鸡店吃汉堡。 未来$N$天，塔塔君想好了要吃的汉堡，且已知第$i$天的汉堡价格为$Pi$。 塔塔炸鸡店为了回馈老客户，吃掉汉堡后可以获得与价格同等数量的汉堡积分，且每$100$个汉堡积分会自动兑换成一张免单券，可以免费吃任意汉堡。

免单券的有效期为$3$天，例如第$1$天获得免单券后，可以在第$2，3，4$天使用，到了第$5$天会自动过期失效，且使用免单券吃掉的汉堡不能获得汉堡积分。(T_T)

塔塔君希望你能帮助他找到一个最省钱的吃汉堡计划:未来$N$天每天要吃一个汉堡的情况下最少要花多少钱。

输入描述

第一行，一个整数T，表示测试用例的组数 ($1≤T≤10$) 对于每组测试用例: 第一行,$1$个整数$N$，表示未来要吃汉堡的天数。 ($1≤N≤1,000$) 接下来N行，每行一个整数Pi，表示第i天多多君要购买的汉堡价格。 ($1≤Pi≤50$)

输出描述

输出一行，一个整数，表示吃完所有汉堡的最小花费。

样例1

输入

1
3
50
50
40			

输出

100

说明

前两天塔塔君直接购买汉堡，共花费$50+50=100$，同时获得$100$汉堡积分。 满$100$汉堡积分后自动兑换一张免单券，剩余$0$汉堡积分。 第三天塔塔君使用免单券吃汉堡，消费$0$，汉堡积分$0$。

样例2

输入

1
8
10
20
30
40
30
30
40
50

输出

200