该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你说的对，但是《原坤》是由新赛道OI自主研发的一款全新开放世界冒险游戏，考虑到游戏已经家喻户晓，所以在此省略两万字的游戏介绍。

一天，旅行者和派蒙在提瓦特的篮球场遇到了神秘人坤坤。

坤坤有一个长度为 $n$ 的序列 $a$。

坤坤认为一个序列 $a$ 是完美的当且仅当 $\gcd(a_1,a_2,...,a_n)=1$。

坤坤现在可以做以下操作任意次：

• 选择一个位置 $i$，将 $a_i$ 变为 $\gcd(a_i,i)$，消耗的体力为 $n-i+1$。

请你帮助坤坤求出使序列 $a$ 完美的最小消耗体力和。

如果你能帮坤坤解答，他会为你高歌一曲：只因你太美！

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n$，表示序列长度。

每个测试用例的第二行包含 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

对于每个测试用例，输出共一行，包含一个整数，表示最小消耗体力和。

1
2
2 4

2

2
3
3 6 9
5
2 2 4 6 8

2
1

见下发大样例 sub3.in

见下发大样例 sub3.out

见下发大样例 sub4.in

见下发大样例 sub4.out

样例 1 解释

花费代价 $2$ 选择位置 $1$，$a_1$ 变为 $1$。

大样例数据

完美序列大样例

数据范围

对于 $30\%$ 的数据，保证 $1\le n\le 20$。

对于 $60\%$ 的数据，保证 $1\le n\le 50$。

对于 $100\%$ 的数据，$1\le t \le 10，1\le n\le 10^5$，$1\le a_i\le 10^9$。