魔法世界中，有一个神奇的能量转化炉，它可以把原料中的能量收集起来，这个炉子有两个炉仓，需要两个炉仓同时运行才能正常工作。不过，炉仓的转化效率是固定的，由于原料的体质不同，收集它们能量所需要的时间也不一样。幸运的是，每块原料的收集过程不需要连续，原料放进炉子后，可以中途拿出来，过一段时间继续收集。
小S是操作能量转化炉的一名魔法学徒，现在她需要尽可能多地将手头的原料进行能量转化。有的原料需要5个小时，有的可能就只需要1个小时。显然如果她只有两块原料一个需要5小时一个需要1小时，那么她只能转化1个小时能量，有一块原料剩下的能量无法转化，但是如果她有更多的原料，就可以更加充分地利用它们，比如她有三块原料分别能用3、3、5小时，她可以先转化两块能用3个小时的原料，使用半个小时后再把其中一块换成能转化5个小时的原料，两个半小时后再把剩下的一块材料换成刚才换下的原料（那块原料还能用2.5个小时），这样总共就可以转化5.5个小时，没有一点浪费。
现在已知原料的数量和每块原料需要转化的时间，请你帮她计算一下最多能转化多长时间吧！
第一行数为数据组数$T$
每组数据包括两行，第一行是一个整数$n$ $(2 ≤ n ≤ 2500)$，表示原料的数量，接下来一行有$n$个正整数，表示每块原料需要转化的时间。
对于每组数据，输出一行，表示最长的转化时间，保留到小数点后1位。
2
2
1 5
3
3 3 51.0
5.5