提示: 欢迎访问OurACM平台。
Problem 1068 An Interesting Set

Accept: 638    Submit: 1165
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Thomas, a mathematician, is interested in a set S consisting of positive integers. Set S is defined as follows:

(1) If a positive integer satisfies the property that the sum of all digits of it is equal to the product of them, then it belongs to S.

(2) If m belongs to S, then 2m belongs to S. Thomas wants to find out the Kth smallest integer in set S. Design a program to solve the problem.

Input

The first line in the input is an integer N representing the number of test cases. The following N lines are N test cases and each line contains an integer K (1<=K<=500).

Output

For each test case, output a line containing an integer that is the Kth smallest integer in set S.

Sample Input

2 5 16

Sample Output

5 22

Source

FJNUPC 2005

Submit  Back  Status  Discuss