[Codeforces Round #827 (Div. 4)] D. Coprime

 

 

---

 

※. 배열 원소의 값이 최대 1000이기 때문에 브루트포스로 모든 원소값의 서로소를 구한다.(1000 * 1000)

 

※. 원소의 값 중 가장 큰 인덱스를 저장해주는 배열을 만든다.

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//4
public class Main {
	static long ans = 0;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringBuilder sb = new StringBuilder();
 		int T = Integer.parseInt(br.readLine());
 		while(T --> 0) {
 			ans = -1;
 			int n = Integer.parseInt(br.readLine());
 			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 			
 			int[] arr = new int[1001];
 			for(int i = 0; i < n; i++) {
 				int idx = Integer.parseInt(st.nextToken());
 				arr[idx] = i+1;
 			}
 			
 			for(int i = 1; i <= 1000; i++) {
 				for(int j = 1; j <= i; j++) {
 					if(arr[i] != 0 && arr[j] != 0 && gcd(i,j) == 1) {
 						ans = Math.max(ans, arr[i]+arr[j]);
 					}
 				}
 			}
 			sb.append(ans).append('\n');
 		}
 		System.out.println(sb);
 	}
 	static int gcd(int a, int b) {
 		if(b == 0)
 			return a;
 		
 		return gcd(b, a%b);
 	}
}