时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
火山哥有一个长度为

的序列

。序列里的数互不相同。
现在他定义
%7D)
为序列删去了第

个到第

个元素之后最大的

值,即为
%20%5Ccup%20(y%2Cn%5D%2Ci%5Cnot%3D%20j%7D%20%5Cgcd(a_i%2Ca_j))
特别地,当序列被删到只剩下一个元素时,
%20%3D%200%7D)
。
现在他想要知道
)
。
输入描述:
第一行一个整数
表示数据组数
第一行一个整数
,意义如题面所示。
接下来一行
个数,分别表示
。
,保证
互不相同。
输出描述:
一行一个整数,表示答案。
示例1
输入
复制
3
1
2
5
5 4 1 8 7
9
1 2 3 4 5 6 7 8 9