思路

关键等价

设整体 LCM 的质因数分解为

题目内容

给定一个长度为n的正整数数组$a_1，a_2,...,a_n$。你需要找到一个连续子数组$[1,r]$，使得该子数组的最小公倍数$(LCM)$等于整个数组的$LCM$，并且该子数组的长度尽可能短。

请输出满足条件的子数组的最小长度。

名词解释 子数组:从原数组中，连续的选择一段元素(可以全选、可以不选)得到的新数组。

最小公倍数$(LCM)$:多个整数的最小公倍数是能被这些数整除的最小正整数。例如

$LCM(2,3)=6.LCM(5,5)=5$。特别地，单个元素的最小公倍数还是它本身。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≦T≦10^4)$代表数据组数，每组测试数据描述如下:

第一行输入整数$n(1≦n≦10^5)$表示数组长度,

第二行输入$n$个正整数$a_1,a_2,...,a_n(1≦a_i≦10^9)$

除此之外，保证单个测试文件的$n$之和不超过$10^5$。

输出描述

对于每组测试数据，输出一个整数表示答案。

样例1

输入

2
3
2 3 6
4
6 4 2 8

输出

1 
4

说明

[样例说明] 第一组数据中，整个数组的$LCM$为$6$。子数组$[3,6]$的$LCM$为$6$，但最短的是单个元素$[6]$，因此输出$1$。