Given an array of n integers, you can perform the following operation any number of time:

Choose an index k such that 0<=k<n-1 and a[k]!=a[k+1] , and replace {a[k], a[k+1]} by a single integer equal to either a[k]%a[k+1] or a[k+1]%a[k], which leads to reduction of size of the resulting array by 1.

Return the smallest possible size of the resulting array by applying the above operation any no. of times.

Example:
a=[1, 1, 2, 3]
=> choose k=2 and replace a[2] and a[3] by a[2]%a[3] = 2%3 = 2
a becomes [1, 1, 2]
=> choose k=1 and replace a[1] and a[2] by a[2]%a[1] = 2%1 = 0
a becomes [1, 0]
=> choose k=0 and replace a[0] and a[1] by a[2]%a[1] = 0%1 = 0
a becomes [0]
Thus minimum possible size is 1