题目描述

给定一个长度为 $n$ 的正整数数组 $a$，你可以进行任意多次如下操作：

• 在 $1 \sim n$ 内选择两个正整数 $x, y$，让 $a_x$ 减 $1$，$a_y$ 加 $1$，需要保证操作后 $a_x, a_y$ 均仍为正数

操作完成后，对 $i = 1 \sim n$，统计有多少 $i$ 满足 $i | a_i$，即 $a_i$ 是 $i$ 的倍数

你希望这个统计结果尽量大，请问这个统计结果的最大值可以达到多少

输入格式

第一行，包含一个正整数 $T$，表示该测试点中的数据组数

对于每组数据：

第一行，包含一个正整数 $n$，表示数组长度

第二行，包含 $n$ 个正整数 $a_i$

输出格式

每组数据输出一行，包含一个整数，表示该组数据的答案

样例

样例输入1

1
4
1 1 2 2

样例输出1

2

样例输入2

1
5
1 1 2 2 3

样例输出2

3

样例解释

对于样例 $1$，一种最优解是将 $a$ 数组最终变成 $[1, 1, 3, 1]$

数据范围

对于 $30\%$ 的数据，$1 \leq n \leq 5, 1 \leq a_i \leq 5$

对于 $60\%$ 的数据，$1 \leq n \leq 100, 1 \leq a_i \leq 100$

对于 $100\%$ 的数据，$1 \leq T \leq 10, 1 \leq n \leq 10^5, 1 \leq a_i \leq 10^5$