407341: GYM102767 G Singhal and Multiplication

Singhal has a sequence of integers $$$a_1 , a_2 , \ldots , a_n$$$.

Recall,

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

$$$ a\pmod n$$$ is the remainder of the Euclidean division of a by n, where a is the dividend and n is the divisor.

A subarray $$$a_i , a_{i+1} , \ldots , a_j $$$ is good if

$$$$$$ (a_i*a_{i+1}*\cdots*a_j)\pmod n = 1 $$$$$$

Formally,

$$$$$$ \Bigl( \prod_{k=i}^j a_k \Bigr)\pmod n = 1$$$$$$

Help him to find if a good subarray is present in his sequence or not. If there are many good subarray tell the smallest possible in length.

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 (1 \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$$$.

Print $$$t$$$ answers to the test cases. Each answer must be consisting of single integer — the smallest possible length of good subarray if present in the sequence , if not output $$$0$$$.

4
3
2 2 6
4
2 2 3 3
2
2 2
3
2 1 2

2
2
0
1

In the first query, possible subarray are —

$$$ (2) - 2\pmod 3 = 2 $$$

$$$ (2) - 2\pmod 3 = 2 $$$

$$$ (6) - 6\pmod 3 = 0 $$$

$$$ (2,2) - (2*2)\pmod 3 = 1 $$$

$$$ (2,6) - (2*6)\pmod 3 = 0 $$$

$$$ (2,2,6) - (2*2*6)\pmod 3 = 0 $$$

Only one good subarray $$$(2,2)$$$ , length - $$$2$$$.

In the second query , only one good subarray $$$(3,3) - (3*3)\pmod 4 = 1$$$ , length - $$$2$$$.

In third query , no good subarray possible.

In fourth query , two good subarray possible —

$$$(1) - 1\pmod 3 = 1 $$$

$$$(2,1,2) - (2*1*2)\pmod 3 = 1 $$$

We have to choose one with smallest length , i.e. $$$1$$$.