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

For any , let be the last five digits before the trailing zeroes in written in base .

For example,

so

so

so

Find for multiple values of .

**Input Format**

First line of each file contains two numbers: (base) and (number of queries). lines follow, each with an integer written in base .

**Constraints**

- Every character in is a valid digit in base ('0'-'9','A'-'Z' for values )

**Output Format**

Output lines. On each line print exactly digits in base - the answer to the -th query. If for some contains less than digits, put the corresponding number of leading zeroes before answer.

**Sample Input**

```
10 3
9
10
20
```

**Sample Output**

```
36288
36288
17664
```