Python3 solution

def ok(p, L):
    sum = 0
    while L > 0:
        sum += L % p
        L //= p
    return sum % p

def solve(p, L):
    L1 = L // p
    r = p - ok(p, L1)
    if r == p:
        r = 0
    if r < L % p:
        return L1 + 1
    else:
        return L1

T = int(input())
for t in range(T):
    p, L = map(int, input().split())
    L += 1
    L1 = L // p
    ans = 0
    if ok(p, L1) == 0:
        ans += L % p
    print(ans + solve(p, L1) * p - 1)

To solve this problem, there are 3 levels to climb:

(1) Know the quick way to calculate ord_p(n!). This goes back to an old problem of counting the tailing zeros of 1000!, which is basically ord_5(1000!) (because ord_2(1000!) is greater and one needs 2*5=10 to get a tailing zero). The quick way is

ord_5(1000!)=200+40+8+1=249.

There are 1000/5=200 multiples of 5, among which there are 200/5=40 multiples of 5^2=25, among which there are 40/5=8 multiples of 5^3=125, among which there is only int(8/5)=1 multiple of 5^4=625, which is 625 itself. No need to count the multiples one by one.

(2) Write n in base-p as

n=n[k]*p^k+n[k-1]*p^(k-1)+...+n[1]*p+n[0].

This helps us find ord_p(n!) mod p. Notice that (the number of multiples of p under n) mod p is n[1]. Likewise, (the number of multiples of p^2 under n) mod p is n[2], ... . Eventually, one obtains

ord_p(n!) mod p = (n[1]+n[2]+...+n[k]) mod p.

(3) Write L also in base-p to figure out how many numbers between 1 and L satisfy ord_p(n!) mod p = 0, i.e., according to step (2), have a digit sum in base-p that is divisible by p. Notice that n[0] is a free variable and n[1] is uniquely determined once n[2]...n[k] are all given. However, make sure the number n does not go beyond the range of 1...L.

well where is the discussions??? please anybody share to me...