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₁, a₂, ..., a_n) is "cool" if the pairs (a₁, a₂), (a₂, a₃), ..., (a_n - 1, a_n) are all cool.

The cows have a sequence of n positive integers, a₁, a₂, ..., a_n. In one move, they may replace some a_i with any other positive integer (there are no other limits on the new value of a_i). 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₁, a₂, ..., a_n (1 ≤ a_i ≤ 10¹⁵).

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.

A single integer, the minimum number of a_i that must be changed to make the sequence cool.