题目背景

几年前的仲夏，身为课代表的 OC 接到了老师的一个任务：为班里的同学拟定一个小组分配方案。显然，大家都喜欢摸鱼，甚至于想找大佬替自己完成任务，心怀正义感的 OC 不想让这种事情发生。

题目描述

OC 找来了班里所有同学的量化考核成绩单，并打算借此为每个同学划分小组。记成绩序列为 $a$，OC 定义下面的小组为优秀的：

1. 小组构成 $a$ 的一个 连续子序列$^{\dagger}$；
2. 记小组内所有成员的成绩的 最小公倍数$^{\ddagger}$ 为 $x$，小组内没有一个成员的成绩等于 $x$。

OC 想要找出优秀小组的成员数量的最大值，但班主任突然找他有事，分身无术的他想请你帮他完成这个任务。

$^{\dagger}$序列 $B$ 构成序列 $A$ 的一个连续子序列，当且仅当序列 $B$ 可通过从序列 $A$ 的开头和结尾中删除若干（可不删或全删）元素得到。
$^{\ddagger}$两个或多个整数公有的倍数叫做它们的公倍数，其中除 $0$ 以外最小的一个公倍数就叫做这几个整数的最小公倍数。

输入格式

输入的第一行包含一个整数 $t$ $(1 \leq t \leq 1000)$，代表测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$ $(2 \leq n \leq 10 ^ 5)$，代表成绩序列的长度。

第二行包含 $n$ 个整数 $a_i$ $(1 \leq a_i \leq 10^9)$，代表第 $i$ 个同学的成绩。

输入保证 $n$ 的总和不超过 $2 \times 10 ^ 5$。

输出格式

对于每一组测试用例，输出一行一个整数 $x$，代表优秀小组成员数的最大值。

4
3
2 3 6
3
2 6 3
4
1234567 1234567 2345678 3456789
8
2 3 5 7 11 13 17 19

2
0
4
8

说明

对于样例 $1$，选择子序列 $2, 3$ 是最优的，其最小公倍数为 $6$，不在 $2, 3$ 中。

对于样例 $2$，注意你不可以选择子序列 $2, 3$，因为他们不连续。

对于样例 $3$，注意最小公倍数可能会很大。