Hansa is throwing a birthday party. Seeing the extravagant parties thrown by her friends in the past, Hansa too decided to do something unique. Being a Computer Engineer herself, she knew just how to do it. She sent password-protected e-invites to T of her friends. Along with each of those e-invites there would be a number and a string. The number represents the base of the string. Their task was to convert the given string to decimal and add the Sum of Digits of that string which would be the password for that invite.
Help her friends find the password so that they can enjoy the party!
Input: First line of input is an integer t, the number of test cases. The following t lines would contain an integer and a string separated by a space.
Output: For each test case, print the sum of digits of the string after changing it to decimal.
Constraints:
1 <= t <= 500
2 <= base <= 36
1 <= |string length| <= 10000
Problem Setter: Rohit Mishra
Test case #1 - 1 in base-27 means (1 x 27^0) = 1, So, sum of digits is 1
Test case #2 - 3201011 in base-4 means (1 x 4^0) + (1 x 4^1) + (0 x 4^2) + (1 x 4^3) + (0 x 4^4) + (2 x 4^5) + (3 x 4^6) = 144051, So, sum of digits is 14
Test case #3 - 5 in base-6 means (5 x 6^0) = 5, So, sum of digits is 5
Test case #4 - ffarpr in base-29 means (27 x 29^0) + (25 x 29^1) + (27 x 29^2) + (10 x 29^3) + (15 x 29^4) + (15 x 29^5) = 318543799, So, sum of digits is 49
Test case #5 - 1 in base-3 means (1 x 3^0) = 1, So, sum of digits is 1
