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

NAo2IDE1Ngo5OSAxNjY2CjEwMDAgMjYyNjI2Mgo5IDEyNDIxNDIx

4
6 156
99 1666
1000 2626262
9 12421421