有n个位置，第i个位子上有 xi 这个数字。

一开始你处在 0 号位，终点是第 n+1 位。

然后按照以下规则进行选择：

如果是第1次选择，那么你可以选择任意一个位置 t1 开始（1<=t1<=n）;

如果是第 j 次选择（j>1）, 所选的位置为 t(j), 而第 j-1 次选择的位置为t(j-1), 那么必须满足 t(j) > t(j-1) 并且 gcd( x(t(j)), x(t(j-1)) ) = 1, 或者直接选择第 n+1 这个位置结束游戏。

请问你做多可以选择几次呢？

提示：gcd(x, y) 表示 x 和 y的最大公约数。

第一行有一个整数T，代表接下来有T组数据。

对于每组数据，第一行有一个整数N，代表有n个位置。

对于每组数据，第二行有N个整数x1,x2,x3…xn。

对于每组数据输出一个整数，占一行，这个整数代表你可以选择的最大次数。

T <= 100

1<=N<=200

1<=xi<=10^6