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 .
Find for multiple values of .
First line of each file contains two numbers: (base) and (number of queries). lines follow, each with an integer written in base .
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.