ILOVEPRODUCT#12422
You're given an array of size , You can perform the following operation once:
Choose a range (l,r) and divide each element in the range by \gcd(a_l,a_{l+1},...,a_r).
Find the range that performing the operation on it gives the minimum final product of the array, if multiple ranges exist output the one with the maximum , and if multiple ranges still exist output the one with the maximum .
The first line consists of a single integer (1 \le t \le 10^5)the number of testcases.
The description of each testcase follows.
The first line of each testcase consists of a single integer (1 \le n \le 10^5)the size of the array .
The next line contains integers a_1 , a_2 , ... , a_n (1 \le a_i \le 10^5).
It is guaranteed that the sum of over all test cases does not exceed 10^5.
The output consists of lines, each containing two numbers and (the leftmost and rightmost indices of the specified range).
Example 1
Subtask ( points): No additional constraints