Let us denote by $G-Value$ the GCD of all elements of an array. Let us call the prefix of size P ($P \ge 1$) of an array A as another array which contains only the first P elements of the array A.

You are given an array A of N integers. You need to remove some prefix of the array so that the $G-Value$ of the remaining array (after removing the prefix) is maximised. You need to print the size of the prefix that should be removed. If there are several possible answers, print the length of minimum size prefix.

Input:

First line contains an integer N, denoting the size of array A. Next line contains N space separated integers denoting the array A.

Output:

Print a single integer, the size of the prefix that should be removed so that the $G-Value$ of the remaining array is maximised. If there are several possible answers, print the length of minimum size prefix.

Constraints:

$2 \le N \le 10^3$

$1 \le A_i \le 10^6$