米哈伊和斯拉维想要观察一群编号为1到n的青蛙，所有青蛙最初位于点0。青蛙i的跳跃长度为a_i。

每秒，青蛙i会向前跳a_i个单位。

在青蛙开始跳跃之前，斯拉维和米哈伊可以放置恰好一个陷阱在一个坐标中，以便捕获所有会经过该坐标的所有青蛙。

不过，孩子们不能远离他们的家太远，因此他们只能将陷阱放在前n个点（即坐标为1到n的点）上，并且他们不能在点0放置陷阱，因为这会让青蛙感到害怕。

你能帮助斯拉维和米哈伊找出使用陷阱最多能捕获多少只青蛙吗？

输入的第一行包含一个整数t（1 ≤ t ≤ 100）——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 2 × 10^5），表示青蛙的数量，同时也是斯拉维和米哈伊可以放置陷阱的最大距离。

每个测试用例的第二行包含n个整数a_1, ..., a_n（1 ≤ a_i ≤ 10^9），表示对应青蛙的跳跃长度。

保证所有测试用例中的n之和不超过2 × 10^5。

对于每个测试用例，输出一个整数——斯拉维和米哈伊使用陷阱最多能捕获的青蛙数量。