C. Singhal and GCD
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For the multiset of positive integers $$$a = {(a_1,a_2, \ldots ,a_k)}$$$ define the Greatest Common Divisor (GCD) of $$$a$$$ as:

$$$gcd(a)$$$ is the maximum positive integer $$$x$$$, such that all integers in multiset $$$a$$$ are divisible on $$$x$$$.

For example, $$$gcd({8,12,16})=4$$$.

Singhal has a sequence consisting of $$$n$$$ integers. He wants to find the subarray of $$$(length > 1)$$$ whose $$$gcd$$$ is maximum possible. If there exist multiple subarrays then choose the largest in length. Help him to find the maximum gcd he can obtain and length of this subarray.

A subarray is the sequence of consecutive elements of the array.

Input

The first line contains a single integer $$$t (1 \le t \le 10^5)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.

Each query contains two lines. The first line contains one integer $$$n (2 \le n \le 10^5)$$$: the number of integers in the sequence, and the second line contains $$$n$$$ integers $$$a_1, \ldots ,a_n (1\le a_i \le 10^9)$$$.

It is guaranteed that the total sum of $$$n$$$ is at most $$$10^5$$$.

Output

Print $$$t$$$ answers to the test cases. Each answer must be consisting of two integers separate by a space — the maximum gcd he can obtain and the length of the maximum subarray.

Example
Input
4
3
3 6 9
3
3 6 4
2
4 8
3
4 4 4
Output
3 3
3 2
4 2
4 3
Note

In the first query, possible subarray with $$$(length > 1)$$$ are :

$$$gcd({3,6}) = 3 \,, gcd({6,9}) = 3 \,, gcd({3,6,9}) = 3. $$$

All the subarray has same $$$gcd = 3$$$, we have to pick the largest length i.e $$$3$$$.

In the second query, possible subarray with $$$(length > 1)$$$ are :

$$$gcd({3,6}) = 3 \,, gcd({6,4}) = 2 \,, gcd({3,6,4}) = 1. $$$

Maximum $$$gcd $$$ we can obtain is $$$3$$$, and the largest length is $$$2$$$.