Find the Minimal Index Sum Pair Divisible by GCD

Given an array of integers, you are required to find a pair of indices \((i, j)\) (1-indexed) such that the greatest common divisor (GCD) of the two elements at these positions divides every integer in the array. In other words, if \(a_i\) and \(a_j\) are the two chosen elements and \(G = \gcd(a_i, a_j)\), then \(G\) must divide each element \(a_k\) of the array.

Among all such valid pairs, you must select the pair with the smallest sum of indices \((i+j)\). If multiple pairs have the same sum, choose the pair with the smaller first index \(i\). It is guaranteed that at least one valid pair exists in each test case.

Mathematically, the condition can be stated as: Find \(i, j\) such that \(\forall k, \; a_k \mod \gcd(a_i, a_j) = 0\), and minimize \(i+j\) (using 1-indexing).

inputFormat

The first line contains a single integer (T), the number of test cases. Each test case is described as follows:\n\nThe first line contains an integer (N), the size of the array.\nThe second line contains (N) space-separated integers representing the array elements.

outputFormat

For each test case, output a single line containing two space-separated integers (i) and (j) (1-indexed) representing the chosen pair of indices.## sample

2
4
10 15 100 90
3
8 4 16

1 2
1 2