a241. 第二題：1 / x 是有限小數

/**********************************************************************************/
/*  Problem: a241 "第二題：1 / x 是有限小數" from 板橋高中2011能力競賽*/
/*  Language: CPP (779 Bytes)                                                     */
/*  Result: AC(4ms, 380KB) judge by this@ZeroJudge                                */
/*  Author: monkey413 at 2012-07-23 11:20:59                                      */
/**********************************************************************************/


#include<iostream>
#include<algorithm>
using namespace std;
int m,n,top=0,upper;
int arr[1000] ;
long long int t=1 ;
int power(int base, int exp)
{
    int tmp=1 ;
    while(exp)
    {
        if(exp&1) tmp*=base ;
        base*=base ;
        exp>>=1 ;
    }
    return tmp ;
}
int main()
{
    for(int i=0 ; i<=13 ; ++i)
    {
        t=power(5,i);
        for(int j=0 ; j<=30; ++j)
        {
            if(t>1000000000) break ;
            else arr[top++]=t ;
            t*=2 ;
        }
    }
    sort(arr,arr+top) ;
    while(cin>>m)
    {
        for(int i=0 ; i<m ; ++i)
        {
            cin >> n ;
            upper=upper_bound(arr,arr+top,n)-arr;
            cout << upper-1 << endl ;
        }
    }
    return 0 ;
}