_{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
```