거듭제곱 계산

x에 x를 30번 곱하면 x31이 된다.

x2 = x × x, x3 = x2 × x, x4 = x3 × x, ..., x31 = x30 × x

만약, 결과를 제곱할 수 있다면, 8번만에 x31을 구할 수 있다.

x2 = x × x, x3 = x2 × x, x6 = x3 × x3, x7 = x6 × x, x14 = x7 × x7, x15 = x14 × x, x30 = x15 × x15, x31 = x30 × x

이전에 나온 계산 결과를 곱하는 방법도 같이 사용한다면 x31은 7번만에 구할 수 있다.

x2 = x × x, x4 = x2 × x2, x8 = x4 × x4, x10 = x8 × x2, x20 = x10 × x10, x30 = x20 × x10, x31 = x30 × x

위의 방법이 곱셈만으로 x31을 구하는 가장 효율적인 방법이다.

만약 나눗셈을 사용할 수 있다면, 연산의 수를 더 줄일 수 있다. x31을 5번의 곱셈과 1번의 나눗셈으로 구할 수 있다.

x2 = x × x, x4 = x2 × x2, x8 = x4 × x4, x16 = x8 × x8, x32 = x16 × x16, x31 = x32 ÷ x

이 방법은 나눗셈이 곱셈만큼 빠를 때 x31을 계산하는 가장 효율적인 방법이다.

x로 시작해서 xn을 만드는데 드는 연산 회수의 최솟값을 구하는 프로그램을 작성하시오. 문제에서 설명한 곱셈과 나눗셈만 사용할 수 있다. 연산의 결과는 항상 x의 양의 제곱수 이어야 한다. 즉, x-3은 나오면 안 된다.

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

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