题目内容

给出一段长度为 $m$ 的正整数序列 {$b_1,b_2,…,b_m$} ;

把下标从 $L$ 到 $R$ 的那截连续片段叫做优美段，条件是这截全体数字满足 $gcd(b_L,b_{L+1},...,b_R)≤R-L+1$ ;

要把整段序列切成 $p$ 截两两没有交集的优美段，并且原序列每个下标都被盖住，目标是让 $p$ 尽量大，打印这个最大的 $p$ 。

输入描述

一份测试文件里会塞进若干组数据。

首行读入一个整数 $q(1 ≦q ≦ 10^4)$ ，用来说明有多少组用例；

另外限制：各组用例的 $m$ 加起来不会超过 $2×10^5$ ；

接下来每一组按下面版式给出：

• 首行读入一个整数 $m(1 ≦ m ≦ 2×10^5)$ ;

• 次行读入 $m$ 个整数 $b_1,b_2,...,b_m(1 ≦b_p≦ 10^9)$

输出描述

每一组用例另起一行打印一个整数，即切成优美段时最多能切出多少截，倘若根本切不出来则打印 $'-1'$ 。

样例1

输入

3
6
6 3 3 3 2 1
4
8 8 8 8
5
1 6 2 2 1

输出

3
-1
3