Time Limit: 5000msMemory Limit: 32768K


通过的连乘,我们可以通过30次操作得到:
  
当我们换一种方式来乘,可以让操作次数边少:
  
当然,上面的还不是最短的:
  
当引入除法之后,会变得更短:
  
如果除法运算的速度与乘法运算相同,那么上式是最有效率的得到的方式。
现在请你们求出通过上述乘除运算得到的最少操作次数。

输入

第一行是一个整数,代表样例数。
接下来行,每行一个整数

输出

对于每组样例,输出一个整数,表示得到的最少操作次数。

4
1
31
70
953

0
6
8
12