Bessie and the cows have recently been playing with "cool" sequences and are trying to construct some. Unfortunately they are bad at arithmetic, so they need your help!

A pair (*x*, *y*) of positive integers is "cool" if *x* can be expressed as the sum of *y* consecutive integers (not necessarily positive). A sequence (*a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>) is "cool" if the pairs (*a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>), (*a*<sub class="lower-index">2</sub>, *a*<sub class="lower-index">3</sub>), ..., (*a*<sub class="lower-index">*n* - 1</sub>, *a*<sub class="lower-index">*n*</sub>) are all cool. 

The cows have a sequence of *n* positive integers, *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>. In one move, they may replace some *a*<sub class="lower-index">*i*</sub> with any other positive integer (there are no other limits on the new value of *a*<sub class="lower-index">*i*</sub>). Determine the smallest number of moves needed to make the resulting sequence cool.
The first line contains a single integer, *n* (2 ≤ *n* ≤ 5000). The next line contains *n* space-separated integers, *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">15</sup>).

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
#From Jasnah bobb31
#From Jasnah bobb31
#From Jasnah bobb31
import sys
def solve():
    N = int(sys.stdin.readline())
    arr = [0] * 5003
    dinpr = [0] * 5003
    ct = [0] * 5003
    dinpr[0] = 0
    for i, num in enumerate(map(int, sys.stdin.readline().split()), start=1):
        arr[i] = num
        while arr[i] % 2 == 0:
            arr[i] //= 2
            ct[i] += 1
    N += 1
    arr[N] = 1
    for i in range(1, N + 1):
        dinpr[i] = i
        for j in range(1, i):
            if arr[j] % arr[i] == 0 and (ct[i] - ct[j] == i - j or ct[i] <= i - j - 1):
                dinpr[i] = min(dinpr[i], dinpr[j] + i - j - 1)
    return dinpr[N] - 1
print(solve())