거듭제곱 계산

$x$에 $x$를 $30$번 곱하면 $x^{31}$이 된다.

$$x^2 = x \times x,\quad x^3 = x^2 \times x,\quad x^4 = x^3 \times x,\quad \dots,\quad x^{31} = x^{30} \times x$$

만약 중간 결과를 제곱할 수 있다면, $8$번의 연산만으로 $x^{31}$을 구할 수 있다.

$$x^2 = x \times x,\quad x^3 = x^2 \times x,\quad x^6 = x^3 \times x^3,\quad x^7 = x^6 \times x,\quad x^{14} = x^7 \times x^7,\quad x^{15} = x^{14} \times x,\quad x^{30} = x^{15} \times x^{15},\quad x^{31} = x^{30} \times x$$

앞서 나온 계산 결과들을 서로 곱하는 방법까지 함께 쓰면 $x^{31}$을 $7$번의 연산으로 구할 수 있다.

$$x^2 = x \times x,\quad x^4 = x^2 \times x^2,\quad x^8 = x^4 \times x^4,\quad x^{10} = x^8 \times x^2,\quad x^{20} = x^{10} \times x^{10},\quad x^{30} = x^{20} \times x^{10},\quad x^{31} = x^{30} \times x$$

이것이 곱셈만으로 $x^{31}$을 구하는 가장 효율적인 방법이다.

만약 나눗셈도 쓸 수 있다면 연산 횟수를 더 줄일 수 있다. $x^{31}$을 곱셈 $5$번과 나눗셈 $1$번으로 구할 수 있다.

$$x^2 = x \times x,\quad x^4 = x^2 \times x^2,\quad x^8 = x^4 \times x^4,\quad x^{16} = x^8 \times x^8,\quad x^{32} = x^{16} \times x^{16},\quad x^{31} = x^{32} \div x$$

이것은 나눗셈이 곱셈만큼 빠를 때 $x^{31}$을 계산하는 가장 효율적인 방법이다.

$x$에서 시작해 $x^n$을 만드는 데 드는 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 문제에서 설명한 곱셈과 나눗셈만 사용할 수 있다. 모든 중간 결과는 항상 $x$의 양의 거듭제곱이어야 한다. 즉 $x^{-3}$ 같은 것이 나와서는 안 된다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 한 줄로 이루어지며, 정수 $n$이 주어진다. $n$은 양의 정수이며 $1000$보다 작거나 같다.

각 테스트 케이스에 대해, $x^n$을 만드는 데 필요한 곱셈과 나눗셈의 최소 횟수를 한 줄에 하나씩 출력한다.