MY CODE:

import time
import math
import sys
def sums(n):
   r = 0
   while n:
       r, n = r + n % 10, n // 10
   return r
def f(n):
    r=0
    s1=0
    while n:
        r, n =  n % 10, n // 10
        s1=s1+math.factorial(int(r))
    return s1

def sf(n):
    return sums(f(n))

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        p=p+1

def sg(i):
    return sums(g(i))

def ssg(n):
    s=0
    for i in range(1,n+1):
        s=s+sg(i)
    return s

q=int(sys.stdin.readline())
out=[]
for i in range(q):
    n1,m1=(sys.stdin.readline()).split()
    n=int(n1)
    m=int(m1)
    v=ssg(n)
    out.append(v%m)
for i in out:
    print(i)

this code was made for question:

Define f(n) as the sum of the factorials of the digits of n. For example, f(342) = 3! + 4! + 2! = 32.

Define sf(n) as the sum of the digits of f(n). So sf(342) = 3 + 2 = 5.

Define g(i) to be the smallest positive integer n such that sf(n) = i. Though sf(342) is 5, sf(25) is also 5, and it can be verified that g(5) is 25.

Define sg(i) as the sum of the digits of g(i). So sg(5) = 2 + 5 = 7.

Further, it can be verified that g (20) is 267 and ∑ sg(i) for 1 ≤ i ≤ 20 is 156.

What is ∑ sg(i) for 1 ≤ i ≤ 150?

Input Format

The first line of each test file contains a single integer q, which is the number of queries per test file. lines follow, each containing two integers separated by a single space: n and m of the corresponding query.

Output Format

Print exactly q lines, each containing a single integer, which is the answer to the corresponding query.

**Sample Input **

2
3 1000000
20 1000000

Sample Output

8
156

MY PROBLEM

This code is not fast enough for all their test cases so, my code was rejected as answer. (They did not specify which test cases they are testing on it.)

So, how efficiency of this code could be increased?

Thanks

PS: output is n modulo m for each entry