from sys import stdout
import os
import io
from collections import deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
def convert (n, base):
if n == 0:
return '0'
nums = []
while n:
n, r = divmod(n, base)
nums.append(str(r))
nums.reverse()
return ''.join(nums)
t: int = int(input())
while t:
t -= 1
p, n = [int(i) for i in input().split()]
result = 0
for ch in convert(n, p):
result += int(ch)
stdout.write(f"{result}\n")
ZnJvbSBzeXMgaW1wb3J0IHN0ZG91dAppbXBvcnQgb3MKaW1wb3J0IGlvCmZyb20gY29sbGVjdGlvbnMgaW1wb3J0IGRlcXVlCgppbnB1dCA9IGlvLkJ5dGVzSU8ob3MucmVhZCgwLCBvcy5mc3RhdCgwKS5zdF9zaXplKSkucmVhZGxpbmUKCmRlZiBjb252ZXJ0IChuLCBiYXNlKToKICAgIGlmIG4gPT0gMDoKICAgICAgICByZXR1cm4gJzAnCiAgICBudW1zID0gW10KICAgIHdoaWxlIG46CiAgICAgICAgbiwgciA9IGRpdm1vZChuLCBiYXNlKQogICAgICAgIG51bXMuYXBwZW5kKHN0cihyKSkKICAgIG51bXMucmV2ZXJzZSgpCiAgICByZXR1cm4gJycuam9pbihudW1zKQogICAgCnQ6IGludCA9IGludChpbnB1dCgpKQoKd2hpbGUgdDoKCXQgLT0gMQoJcCwgbiA9IFtpbnQoaSkgZm9yIGkgaW4gaW5wdXQoKS5zcGxpdCgpXQoJcmVzdWx0ID0gMAoJZm9yIGNoIGluIGNvbnZlcnQobiwgcCk6CgkJcmVzdWx0ICs9IGludChjaCkKCQoJc3Rkb3V0LndyaXRlKGYie3Jlc3VsdH1cbiIp