[Solution] Coprime Codeforces Solution | Solution Codeforces

D. Coprime

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Given an array of 𝑛$n$ positive integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤1000$1\le a_i\le 1000$). Find the maximum value of 𝑖+𝑗$i+j$ such that 𝑎𝑖$a_i$ and 𝑎𝑗$a_j$ are coprime,†${}^{†}$ or −1$-1$ if no such 𝑖$i$, 𝑗$j$ exist.

For example consider the array [1,3,5,2,4,7,7]$[1,3,5,2,4,7,7]$. The maximum value of 𝑖+𝑗$i+j$ that can be obtained is 5+7$5+7$, since 𝑎5=4$a_5=4$ and 𝑎7=7$a_7=7$ are coprime.

†${}^{†}$ Two integers 𝑝$p$ and 𝑞$q$ are coprime if the only positive integer that is a divisor of both of them is 1$1$ (that is, their greatest common divisor is 1$1$).

Input

The input consists of multiple test cases. The first line contains an integer 𝑡$t$ (1≤𝑡≤10$1\le t\le 10$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer 𝑛$n$ (2≤𝑛≤2⋅105$2\le n\le 2\cdot {10}^5$) — the length of the array.

The following line contains 𝑛$n$ space-separated positive integers 𝑎1$a_1$, 𝑎2$a_2$,..., 𝑎𝑛$a_n$ (1≤𝑎𝑖≤1000$1\le a_i\le 1000$) — the elements of the array.

It is guaranteed that the sum of 𝑛$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, output a single integer  — the maximum value of 𝑖+𝑗$i+j$ such that 𝑖$i$ and 𝑗$j$ satisfy the condition that 𝑎𝑖$a_i$ and 𝑎𝑗$a_j$ are coprime, or output −1$-1$ in case no 𝑖$i$, 𝑗$j$ satisfy the condition.

Note

For the first test case, we can choose 𝑖=𝑗=3$i=j=3$, with sum of indices equal to 6$6$, since 1$1$ and 1$1$ are coprime.

For the second test case, we can choose 𝑖=7$i=7$ and 𝑗=5$j=5$, with sum of indices equal to 7+5=12$7+5=12$, since 7$7$ and 4$4$ are coprime.