전자레인지 타이머

Kenny의 주방에는 버튼 하나로 조작하는 독특한 타이머가 달린 전자레인지가 있다. 가열을 시작하려면 버튼을 한 번 이상 누른다. 처음 누르면 타이머가 $1$분으로 설정된다. 곧바로 한 번 더 누르면 $2$분이 더해져 합계가 $3$분이 된다. 또 곧바로 누르면 $4$분이 더해지며, 이런 식으로 이어진다. 멈춤 없이 $k$번째로 누르면 타이머에 $2^k$분이 더해진다.

버튼만으로는 설정할 수 없는 시간이 있어 보인다. 예를 들어 $2$분은 어떻게 설정할까? 1초 동안 멈추면 누른 횟수 카운터를 초기화할 수 있다. 누르고, 1초 멈춘 뒤, 다시 누르면 타이머가 $2$분으로 설정된다. 또 다른 예로 누르기, 누르기, 멈춤, 누르기, 누르기, 누르기를 하면 전체 시간은 $1+2+1+2+4=10$분이다.

Kenny는 음식을 정확히 $x$분 동안 가열해야 한다. 타이머를 설정하는 데 필요한 1초 멈춤의 최소 횟수를 구하여라. 시간을 소비하는 것은 멈춤뿐이며, 버튼을 누르는 시간은 무시한다.

첫째 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 10^4$)가 주어진다. 이후 $t$개의 줄에 각각 정수 $x$ ($1 \le x \le 10^{18}$)가 한 개씩 주어진다. $x$는 Kenny가 음식을 가열해야 하는 시간(분)이다.

각 테스트 케이스마다 타이머를 $x$분으로 설정하는 데 필요한 1초 멈춤의 최소 횟수를 한 줄에 하나씩 출력한다.

첫 번째 테스트 케이스에서는 멈춤이 필요 없다. Kenny는 버튼을 한 번만 누르면 된다.

두 번째 테스트 케이스에서는 누르기, 멈춤, 누르기로 타이머를 $2$분으로 설정할 수 있다.

세 번째 테스트 케이스에서는 버튼을 두 번 눌러 타이머를 $3$분으로 설정할 수 있다.

네 번째 테스트 케이스에서는 누르기, 누르기, 멈춤, 누르기로 $1 + 2 + 1 = 4$분을 설정할 수 있다.