Speak your mind!

The Shakespeare Programming Language (SPL) is an esoteric programming language whose source code looks like a play by Shakespeare. A typical SPL program looks like this.

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)

In SPL a number is written with nouns and adjectives. A noun with a positive meaning is 1, and a noun with a negative meaning is -1. Every adjective placed in front of the noun doubles the value. The articles "a", "an" and "the" in front of a noun are optional.

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

An integer that is not a power of two is built with arithmetic. "the sum of (A) and (B)" is A + B, and "the difference between (A) and (B)" is A - B, where (A) and (B) are numbers written in the Shakespearean form. Neither phrase takes an adjective of its own, so "the mighty sum of hero and king" is invalid. The original SPL has multiplication and division as well, but this problem uses only addition and subtraction.

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

Bryan likes writing programs in SPL. Unlike other programmers he dislikes wordy code, so he looks for the expression that uses the fewest words.

Words are counted as follows. An article in front of a noun may be dropped, so it never counts. A noun carrying $k$ adjectives is $k+1$ words and its value is $2^k$ or $-2^k$. The phrases "the sum of" and "the difference between" are fixed and have to be written out. Joining A and B with either phrase therefore costs the words of A plus the words of B plus 4: three words for the phrase itself and one for the "and" between the two parts.

Given an integer $N$, write a program that finds the minimum number of words needed to express $N$ in the Shakespearean form.

The first line contains the number of test cases $T$. ($1 \le T \le 10000$)

Each of the next $T$ lines contains one integer $N$. ($|N| \le 50000$)

For each test case, print the minimum number of words on its own line.