Server Time: Wed Feb 26, 2020 1:57 pm
Welcome ( logout
A - Number System Crackdown
Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

For each case you are given a number system base and a string of digits(a valid number in that base). You’ve to print this number in decimal number system, that is, base 10. Print the number modulo 1000003.

Input

Input starts with an integer T (≤ 300), denoting the number of test cases.

Each case has a line containing an integer B (2 ≤ B ≤ 9) denoting the base and a string of digits. Length of the string will be maximum 10^4.

Output

For each case, print the number in decimal system.

Sample Input

Output for Sample Input

2

4 23

7 2366666666666666666666666

Case 1: 11

Case 2: 853574

 

 


Problem Setter: S. M. IJAZ-UL-AMIN CHOWDHURY
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan