牛牛拥有 根木棒，长度分别为 现在，牛牛可以做若干次操作，每一次操作，可以选择任意两根木棒，将它们拼接在一起，假设选择的两根木棒的长度分别为 ，那么拼接后的木棒长度为 那么，在停止操作之后，牛牛最多可以得到几根长度相同的木棒？

输入描述:

本题为多组测试数据，第一行输入一个正整数 ，代表测试数据的组数。接下去 行，每行一个正整数 ，代表木棒的数量，同时表明，木棒的长度分别为

输出描述:

对于每组测试数据，一行输出一个整数代表答案。