Project Euler #160: Factorial trailing digits

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

Sample Output

36288
36288
17664