作为ACM协会的成员，这段时间最盼望的日子就是新生赛那几天。成绩再过几个小时就公布了，会长想给一直顽强拼搏的的参赛队员发一笔奖金。
但是会长就在考虑一个问题：如果每个同学的奖金额都知道，最少需要准备多少张人民币，才能在给每位同学发奖金的时候都不用会长找零呢？
这里假设同学的奖金都是正整数，单位元，人民币一共有100元、50元、20元、10元、5元和1元六种。
输入描述:
第一行为正整数T，输入数据包含T个测试实例，
每个测试实例的第一行是一个整数n（n<100），表示同学的人数，然后是n个同学的奖金。
输出描述:
对于每个测试实例输出一个整数x,表示至少需要准备的人民币张数。每个输出占一行。