题目描述
风情成功打开女神给他的信封，女神表示想与风情共享烛光晚餐，并且在饭后来上一把紧张、刺激的成人跳棋。
很快就到了赴约的日子，风情早早的到思源大酒店三楼和女神见面。接下来就是紧张、刺激的成人跳棋时刻。成人跳棋与普通跳棋差别极大，因为激情、刺激。其规则如下：
有一条直线和$n$颗棋子，它们最初都位于$0$点，第$i$颗棋子每秒钟的跳跃距离为$a[i]$。每秒钟，棋子$i$向前跳跃$a[i]$个单位长度。在开始游戏之前，风情和女神可以在一个坐标点上(这条直线上)放一个标记，若一个棋子在停留在标记点上，则该棋子将被摧毁。虽然风情荣获了女神的芳心，但是女神不想贪玩(虽然风情想)，所以标记点只能放置在$1$和$n$之间的坐标点上，并且不能放在$0$点上。你能帮助风情和女神找出使用标记最多能摧毁几颗棋子吗？
跳棋虽好，可不要贪玩哟~
输入
第一行一个整数$t(1\le t\le 100)$ —$t$组测试数据。
每组测试数据第一行一个整数$n(1\le n\le 2\cdot 10^{5} )$ —跳棋个数。
第二行为$n$个整数分别是$a_{a} ,...,a_{n}(1\le a_{i}\le 10^{9} )$ —每个跳棋每秒跳的距离。
7
5
1 2 3 4 5
3
2 2 2
6
3 1 3 4 9 10
9
1 3 2 4 2 3 7 8 5
1
10
8
7 11 6 8 12 4 4 8
10
9 11 9 12 1 7 2 5 8 10
提示
在第一个测试案例中，跳棋的跳跃情况如下：
跳棋 1：0→1→2→3→4→⋯
跳棋 2：0→2→4→6→8→⋯
跳棋 3：0→3→6→9→12→⋯
跳棋 4：0→4→8→12→16→⋯
跳棋 5：0→5→10→15→20→⋯
因此，如果风情和女神在坐标 4 处设置标记点，他们可以摧毁到三颗跳棋 ：跳棋 1、2 和 4。可以证明他们无法再摧毁到更多的跳棋 。 在第二个测试案例中，风情和女神可以在坐标 2 处设置标记点，并立即摧毁三颗跳棋 。