속마음을 말하라!

문제

셰익스피어 프로그래밍 언어(Shakespeare Programming Language, SPL)는 소스 코드가 셰익스피어의 희곡처럼 보이는 난해한 프로그래밍 언어다. SPL로 쓴 전형적인 프로그램은 다음과 같다.

The Infamous Hello World Program.

Romeo, a young man with a remarkable patience.
Juliet, a likewise young woman of remarkable grace.
Ophelia, a remarkable woman much in a dispute with Hamlet.
Hamlet, the flatterer of Andersen Insulting A/S.

Act I: Hamlet's insults and flattery.
Scene I: The insulting of Romeo.

[Enter Hamlet and Romeo]

Hamlet:
 You lying stupid fatherless big smelly half-witted coward!
 You are as stupid as the difference between a handsome rich brave
 hero and thyself! Speak your mind!
(The rest omitted)

SPL에서 수는 명사와 형용사로 나타낸다. 긍정적인 뜻의 명사는 1을, 부정적인 뜻의 명사는 -1을 나타낸다. 명사 앞에 형용사를 하나 붙일 때마다 값이 두 배가 된다. 명사 앞의 관사 "a", "an", "the"는 써도 되고 쓰지 않아도 된다.

an angel = 1
curse = -1
a beautiful sweet rose = 2 * 2 * 1 = 4
dirty rotten dusty fat war = 2 * 2 * 2 * 2 * (-1) = -16

2의 거듭제곱이 아닌 정수는 연산으로 만든다. "the sum of (A) and (B)"는 A + B를, "the difference between (A) and (B)"는 A - B를 뜻하고, (A)와 (B)에는 셰익스피어 식으로 쓴 수가 들어간다. 이 두 표현 자체에는 형용사를 붙일 수 없다. 예를 들어 "the mighty sum of hero and king"은 올바르지 않다. 원래 SPL에는 곱셈과 나눗셈도 있지만, 이 문제에서는 덧셈과 뺄셈만 쓴다.

the sum of happy lovely honest golden mighty hero and bad smooth cunning pony
    = 2 * 2 * 2 * 2 * 2 * 1 + 2 * 2 * 2 * 1 = 40
the difference between gentle golden peaceful handsome charming happy King
    and the sum of bad hero and lying misused beggar
    = 2 * 2 * 2 * 2 * 2 * 2 * 1 - (2 * 1 + 2 * 2 * (-1)) = 66

브라이언은 SPL로 프로그램 만드는 것을 좋아한다. 다만 다른 프로그래머와 달리 코드가 장황해지는 것을 싫어해서, 단어를 가장 적게 쓰는 표현을 찾으려고 한다.

단어는 다음과 같이 센다. 명사 앞의 관사는 생략해도 되므로 세지 않는다. 형용사 $k$ 개를 붙인 명사 하나는 $k+1$ 개의 단어이고, 그 값은 $2^k$ 또는 $-2^k$ 이다. 반면 "the sum of"와 "the difference between"은 정해진 표현이라 그대로 적어야 한다. 그래서 A와 B를 둘 중 한 표현으로 묶으면 전체 단어 수는 A의 단어 수와 B의 단어 수를 더한 값에 4를 더한 값이 된다. 표현 자체가 세 단어이고, 사이에 들어가는 "and"가 한 단어이다.

정수 $N$ 이 주어질 때, $N$ 을 셰익스피어 식으로 나타내는 데 필요한 단어의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다. ( $1 \le T \le 10000$ )

다음 $T$ 개의 줄에 정수 $N$ 이 하나씩 주어진다. ( $|N| \le 50000$ )

출력

각 테스트 케이스마다 필요한 단어의 최소 개수를 한 줄에 하나씩 출력한다.