Project Euler #248: Numbers for which Euler’s totient function equals 13!

_{This problem is a programming version of Problem 248 from projecteuler.net}

The first number for which is .
Perform several queries each of which is to find the -th number for which .

The time restriction is a double of the usual time restriction.

Input Format

The first line of each test file contains two integers separated by single spaces, which are and , where is the number of queries. lines follow, each containing the corresponding .

Constraints

number of of such 's for which

Output Format

Print exactly lines, with the answer to the corresponding query on each line.

Sample Input 0

6227020800 1
1

Sample Output 0

6227180929