부호 있는 이진 전개

어떤 정수 $n$의 이진 전개란, 다음 세 조건을 모두 만족하는 '자릿수'의 수열 $a_k a_{k-1} \ldots a_1 a_0$을 말한다.

1. 각 자릿수 $a_0, a_1, \ldots, a_k$는 $1$, $0$, $-1$ 중 하나이다.
2. 가장 높은 자리의 자릿수 $a_k$는 $0$이 아니다.
3. $n = a_k \cdot 2^k + a_{k-1} \cdot 2^{k-1} + \cdots + a_1 \cdot 2 + a_0$.

한 정수는 서로 다른 여러 이진 전개를 가질 수 있다. 이 모든 전개 중에서 $0$이 아닌 자릿수의 개수가 가장 적은 것을 최적 전개라고 부른다. 예를 들어 $-1$을 편의상 $\overline{1}$로 나타내면, $15$의 이진 전개에는 $1000\overline{1}$, $1111$, $100\overline{1}1$ 등이 있다. 이 가운데 첫 번째 $1000\overline{1} = 16 - 1 = 15$는 $0$이 아닌 자릿수가 $2$개뿐이므로 $15$의 최적 전개이다.

주어진 정수 $n$에 대해, 그 최적 이진 전개에 들어 있는 $0$이 아닌 자릿수의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 정수 $r$ ($1 \le r \le 500$)이 주어진다. 둘째 줄에는 $r$개의 십진수 자리로 이루어진 정수 $n$이 주어진다. $n$은 가장 높은 자리부터(즉 일반적인 표기 순서로) 적혀 있으며, $0$이 아닌 자릿수로 시작한다.

$n$의 최적 이진 전개에 들어 있는 $0$이 아닌 자릿수의 개수를 한 줄에 출력한다.