Dividing the sequence

Time Limit: 1 Second    Memory Limit: 65536 KB

“In mathematics,  a  geometric  progression,  also  known  as  a  geometric  sequence,  is  a  sequence  of numbers  where  each  term  after  the  first  is  found  by  multiplying  the  previous  one  by  a  fixed  non‐zero number called the common ratio. For example, the sequence 2, 6, 18, 54, ... is a geometric progression with common ratio 3.” 

 

Now consider the sequence S of positive integers. Let K be the smallest number, so S can be divided into K continuous subsequence s1, s2 ... sk, while satisfying the following condition: 

For all i, 1 ≤ i ≤ K, si is a geometric progression with a positive integer common ratio. 

We call such K, Minimum Divide Number (MDN) of S. For instance consider S to be (1, 2, 4, 12, 24, 48, 96). The sequence S can be divided into sets of geometric progressions in two different methods. The MDN for this sequence is 2. 

s1 = (1, 2), s2 = (4, 12), s3 = (24, 48, 96) 

s1 = (1, 2, 4), s2 = (12, 24, 48, 96) 

You are given a sequence of non‐negative integers. You have to replace all zeros with positive integer in such a way that MDN of resulting sequence is the minimum possible. 

 

Input

The  first  line  contains  T  (T  ≤  100),  the  number  of  test  cases.  Each  test  consists  of  two  lines.  First  line contains an integer N (1 ≤ N ≤ 10⁵), the length of sequence. Second line contains N integers ai  (0 ≤ a_i  ≤ 10⁹), the numbers in the sequence. 

 

Output

For each test, print the minimum MDN of sequence for all replacing of zeros with positive integers.  

 

Sample Input

3
4
2 0 8 0
6
2 0 0 8 0 32
8
1 1 2 4 16 32 64 5

Sample Output

1
2
4

Submit

Source: AUT 2012