for _ in range(int(input())):
    (n,m)=(int(x) for x in input().split())
    s=str(n)
    ans=len(s)
    req={}
    mod=int(1e9+7)
    for i in s:
        req[10-int(i)]=req.get(int(i),0)+1
    cnt=0
    while(cnt<m):
        cnt+=1
        temp=req.get(cnt,0)
        
        if (temp>0):
            ans=(ans+temp)%mod
            req[cnt+9]=(req.get(cnt+9,0)+temp)%mod
            req[cnt+10]=(req.get(cnt+10,0)+temp)%mod
    print(ans)