CF1742D Coprime

Given an array of $ n $ positive integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 1000 $ ). Find the maximum value of $ i + j $ such that $ a_i $ and $ a_j $ are coprime, $ ^{\dagger} $ or $ -1 $ if no such $ i $ , $ j $ exist. For example consider the array $ [1, 3, 5, 2, 4, 7, 7] $ . The maximum value of $ i + j $ that can be obtained is $ 5 + 7 $ , since $ a_5 = 4 $ and $ a_7 = 7 $ are coprime. $ ^{\dagger} $ Two integers $ p $ and $ q $ are [coprime](https://en.wikipedia.org/wiki/Coprime_integers) if the only positive integer that is a divisor of both of them is $ 1 $ (that is, their [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) is $ 1 $ ).

The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 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 \leq n \leq 2\cdot10^5 $ ) — the length of the array. The following line contains $ n $ space-separated positive integers $ a_1 $ , $ a_2 $ ,..., $ a_n $ ( $ 1 \leq a_i \leq 1000 $ ) — the elements of the array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

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 $ in case no $ i $ , $ j $ satisfy the condition.

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