# Arup Guha
# 2/24/2025
# Alternate Solution to 2025 COP 4516 Spring Final Individual Contest Problem:
#                     Divisor Series

# Returns the prime factorization of n.
def primefact(n):

    i = 2

    # Store result her.
    res = []

    # Try all primes.
    while i*i <= n:

        # Try to see if i divides evenly into what's left.
        exp = 0
        while n%i == 0:
            exp += 1
            n = n//i

        # Valid term, add it.
        if exp > 0:
            res.append(i)
            res.append(exp)

        # Go to next.
        i += 1

    # Very last term.
    if n > 1:
        res.append(n)
        res.append(1)

    # Return it.
    return res

# Process cases.
def main():

    # Here I add in all the prime factorizations of the numbers from 2 to
    # a million.
    allp = []
    allp.append([])
    allp.append([])
    for i in range(2, 1000001):
        allp.append(primefact(i))

    # Process cases.
    nC = int(input())
    for loop in range(nC):

        # Get input.
        toks = input().split()
        n = int(toks[0])
        d = int(toks[1])

        # store prime factorization of d as a map.
        dlist = primefact(d)

        res = 0

        # Running my sum from 1 to n.
        for i in range(1, n+1):

            # Find all unique primes in both i and d.
            plist = set()
            for j in range(0, len(dlist), 2):
                plist.add(dlist[j])
            for j in range(0, len(allp[i]), 2):
                plist.add(allp[i][j])

            # Storing # of divisors in tmp.
            tmp = 1

            # Number to prime factorize.
            tot = i*d

            # This is the only list of primes we need to check.
            for x in plist:

                # See how many times x divides into tot and divide it out.
                exp = 0
                while tot%x == 0:
                    exp += 1
                    tot = tot//x

                # Update number of divisors.
                tmp = tmp*(exp+1)

            # This was just to make sure I didn't mess up...
            if tot > 1:
                print("ERROR")

            # Add into running tally.
            res += tmp

        # Ta da!
        print(res)

# Run it!           
main()