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