BEANALGO - Think Different

no tags 

Exponentiating by squaring is a general method for fast computation of large integer powers of a number.The same idea allows fast computation of large exponents.

For example, the evaluation of

     x^13 = ((x^2 · x)^2)^2 · x

This algorithm needs only 5 multiplications instead of 12 (13-1).

Write a program that reads the parameters of the algorithm from the standard input, computes the number of multiplications we need, and writes the result to the standard output.

Input

The input begins with the integer t, the number of test cases. Then t test cases follow. For each test case the first and only line of the input contains exactly one integer n.

0 <= n <= 10^18

Output

For each test case the output contains exactly one integer equal to the number multiplications we have to compute in this given algorithm.

Example

Input:
3
3
5
1

Output:
2
3
4

hide comments
Aditya Pandey: 2012-07-01 17:35:31

gud job dear keep going :)

Aradhya: 2012-07-01 17:35:31

But why there is a lang restriction :D it would be good to open it for all :)

Aradhya: 2012-07-01 17:35:31

Tutorial for sure :)
@tjandra: :D :D may be :P

MR. BEAN : 2012-07-01 17:35:31

nice problem :)

jaans: 2012-07-01 17:35:31

Tutorial for sure :D
@tjandra:: +1 with you :)

Francky: 2012-07-01 17:35:31

if n==0:
we don't need any multiplication!-> 0
RE -> Ok.. DOne!!

Last edit: 2012-07-01 09:57:00
Rajesh Kumar: 2012-07-01 17:35:31

Ans for 0???

Francky: 2012-07-01 17:35:31

Tutorial problem for sure. 0.00 with scanf/printf and simple way.
I think it should be open for all language and add a little more time for slow ones.

(Tjandra Satria Gunawan)(曾毅昆): 2012-07-01 17:35:31

nice problem :) but will be more fun if you increase limit for n to 10^100 or 10^1000 :D


Added by:Mrs. Bean
Date:2012-07-01
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own Problem