Okay. Before we begin, a hint : This one's taken from somewhere. Word to word. Google comes to mind, doesn't it? Here goes:  
For the heck of it, we define a new sequence as the infinite sequence of all integers, in ascending order, that can represented as any positive integer power of 5 (i.e 5k where k is a positive integer) or as a sum of distinct positive integer powers of 5 (i.e 5a1 + 5a2 + 5a3 + ... , where a1, a2, a3, ... are distinct positive integers). All the numbers in the lucky sequence are called lucky numbers. The first few numbers are 5, 25, 30, 125, 130, 150, ... Given n your task is to find the nth number in the sequence. 


 Input 

First line of input contains an integer t, t ≤ 200, representing the number of test- cases. Then t lines follow each containing one integer n, 1 ≤ n ≤ 8000. 


 Output 

For each test case output the "Case#x" followed by nth number on a separate line. Answers will fit in a 32-bit signed integer. 



 Sample 

Input
4 
1 
2 
3 
9 

Output
5 
25 
30 
630
# imports
import sys
import StringIO
import math

class Problem(object):
    def __init__(self, reader):        
        self.reader = reader

    def run(self):          
        test_cases = int(self.reader.readline().strip())
        for test_case in range(test_cases):
            lucky_number = 0
            number = int(self.reader.readline().strip())            
            binary = bin(number)
            try:        
                binary_num = binary[2:]
            except:
                binary_num= test_case                

            binary_len = len(binary_num)             
            for idx, char in enumerate(binary_num):
                if char == '1' :
                    lucky_number = lucky_number + math.pow(5,  binary_len - idx)                        
                
            print int(lucky_number)

# Main entry point
############################################################ 
if __name__ == "__main__":
    data = sys.stdin

    problem = Problem(data)
    problem.run()