You are given positive integers $N$ and $D$. You may perform operations of the following two types:
- add $D$ to $N$, i.e. change $N$ to $N+D$
- change $N$ to $\mathop{\mathrm{digitsum}}(N)$
Here, $\mathop{\mathrm{digitsum}}(x)$ is the sum of decimal digits of $x$. For example, $\mathop{\mathrm{digitsum}}(123)=1+2+3=6$, $\mathop{\mathrm{digitsum}}(100)=1+0+0=1$, $\mathop{\mathrm{digitsum}}(365)=3+6+5=14$.
You may perform any number of operations (including zero) in any order. Please find the minimum obtainable value of $N$ and the minimum number of operations required to obtain this value.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $N$ and $D$.

-----Output-----
For each test case, print a single line containing two space-separated integers — the minimum value of $N$ and the minimum required number of operations.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N, D \le 10^{10}$

-----Subtasks-----
Subtask #1 (30 points): $1 \le N, D \le 100$
Subtask #2 (70 points): original constraints

-----Example Input-----
3
2 1
9 3
11 13

-----Example Output-----
1 9
3 2
1 4

-----Explanation-----
Example case 1: The value $N=1$ can be achieved by 8 successive "add" operations (changing $N$ to $10$) and one "digit-sum" operation.
Example case 2: You can prove that you cannot obtain $N=1$ and $N=2$, and you can obtain $N=3$.
The value $N=3$ can be achieved by one "add" and one "digitsum" operation, changing $9$ to $12$ and $12$ to $3$.  
Example case 3: $N=1$ can be achieved by operations "add", "add", "digitsum", "digitsum": $11 \rightarrow 24 \rightarrow 37 \rightarrow 10 \rightarrow 1$.

Difficulty: interview

Starter code:

Solutions:
from collections import deque 
T=int(input())
def break_down(num):
    count=0
    while(len(num)!=1):
        temp=0
        for i in range(0,len(num)):
            temp=temp+int(num[i])
        num=str(temp)
        count=count+1
    return (int(num),count)
def digit_sum(num):
    temp=0
    for i in range(0,len(num)):
        temp=temp+int(num[i])
    num=temp
    return (num)
while(T):
 queue=deque()
 count_n=0
 count_d=0
 T=T-1
 N,d=[i for i in input().split()]
 n,count_n=break_down(N)
 D,count_D=break_down(d)
 dic={}
 if(D==1 or D==2 or D==4 or D==5 or D==7 or D==8):
     mini=1 
 elif(D==3 or D==6):
     mini=min(digit_sum(str(n+3)),digit_sum(str(n+6)),digit_sum(str(n+9)))
 else:
     mini=n
 queue.append((int(N),0))
 ele=int(N)
 count=0
 while(len(queue)!=0):
     ele,count=queue.popleft()
     if(ele==mini):
         break
     else:
         if(len(str(ele))==1):
             temp1=ele+int(d)
             queue.append((temp1,count+1))
         else:
             temp2=digit_sum(str(ele))
             temp1=ele+int(d)
             queue.append((temp2,count+1))
             queue.append((temp1,count+1))
 print(ele,count)

def ds(n):
    num_str = str(n)
    sum = 0
    for i in range(0, len(num_str)):
        sum += int(num_str[i])
    return sum

t = int(input())

for _ in range(t):
	n,d = input().split()
	n = int(n)
	d = int(d)

	s = set()
	temp = n
	for i in range(500000):
		if temp<=9:
			if not temp in s:
				s.add(temp)
				temp = temp+d
			else:
				break
		else:
			temp = ds(temp)

	s = sorted(s)
	k = s[0]

	q = []
	ans = 0 
	q.append((n,1))
	while len(q) != 0:
		num = q[0][0]
		step = q[0][1]
		q.pop(0)
		if num is k:
			ans = step-1
			break
		q.append((num+d,step+1))
		q.append((ds(num),step+1))
		
	print(str(k)+" "+str(ans))


from collections import defaultdict
def digitSum(n):
    n=str(n)
    s=0
    for i in range(len(n)):
        s+=int(n[i])
    return s
def solve(n,d):
    queue=[[n,0]]
    has=defaultdict(int)
    i=0
    while i<10000 and len(queue)!=0:
        t=queue.pop(0)
        if t[0]<10:
            if t[0] not in has:
                has[t[0]]=t[1]
        else:
            queue.append([digitSum(t[0]),t[1]+1])
        queue.append([t[0]+d,t[1]+1])
        i+=1
    print(min(has),has[min(has)])
            
    
for _ in range(int(input())):
    n,d=map(int,input().split())
    solve(n,d)
    


def disum(x):
    x=str(x)
    sum=0
    for i in range(len(x)):
        sum+=int(x[i])
    return sum
for _ in range(int(input())):
    n,d=map(int,input().split())
    ans={}
    souma=[(n,0)]
    ushijima=1
    i=0
    while i<10000:
        nakiri=souma.pop(0)
        if nakiri[0]<10:
            if nakiri[0] not in ans:
                ans[nakiri[0]]=nakiri[1]
        else:
            souma.append((disum(nakiri[0]),nakiri[1]+1))
        souma.append((nakiri[0]+d,nakiri[1]+1))
        i+=1
    print(min(ans),ans[min(ans)])


def disum(x):
    x=str(x)
    sum=0
    for i in range(len(x)):
        sum+=int(x[i])
    return sum
for _ in range(int(input())):
    n,d=map(int,input().split())
    ans={}
    souma=[(n,0)]
    ushijima=1
    i=0
    while i<100000:
        nakiri=souma.pop(0)
        if nakiri[0]<10:
            if nakiri[0] not in ans:
                ans[nakiri[0]]=nakiri[1]
        else:
            souma.append((disum(nakiri[0]),nakiri[1]+1))
        souma.append((nakiri[0]+d,nakiri[1]+1))
        i+=1
    print(min(ans),ans[min(ans)])


def disum(x):
    x=str(x)
    sum=0
    for i in range(len(x)):
        sum+=int(x[i])
    return sum
for _ in range(int(input())):
    n,d=map(int,input().split())
    ans={}
    souma=[(n,0)]
    ushijima=1
    i=0
    while i<1000:
        nakiri=souma.pop(0)
        if nakiri[0]<10:
            if nakiri[0] not in ans:
                ans[nakiri[0]]=nakiri[1]
        else:
            souma.append((disum(nakiri[0]),nakiri[1]+1))
        souma.append((nakiri[0]+d,nakiri[1]+1))
        i+=1
    print(min(ans),ans[min(ans)])


def dSum(n):
    ans = 0
    while(n>0):ans+=n%10;n//=10
    return ans
def solve(n,d,step,ans):
    if(n<10):ans[n] = min(ans[n],step)
    left = dSum(n);right = n+d
    if(step>13):return step
    solve(left,d,step+1,ans);solve(right,d,step+1,ans)
for T in range(int(input())):
    N,D = [int(x) for x in input().split()];ans = {}
    for i in range(10):ans[i] = 100
    solve(N,D,0,ans);x,y = [100,100]
    for i,j in ans.items():
        if(j!=100):x,y = i,j;break
    print(x,y)

def dSum(n):
    ans = 0
    while(n>0):
        ans+=n%10
        n//=10
    return ans

def solve(n,d,step,ans):
    if(n<10):
        ans[n] = min(ans[n],step)
    left = dSum(n)
    right = n+d
    if(step>13):
        return step
    solve(left,d,step+1,ans)
    solve(right,d,step+1,ans)

for T in range(int(input())):
    N,D = [int(x) for x in input().split()]
    ans = {}
    for i in range(10):
        ans[i] = 100
    solve(N,D,0,ans)
    x,y = [100,100]
    for i,j in ans.items():
        if(j!=100):
            x = i
            y = j
            break
    print(x,y)

t = int(input())

def digisum(a):
    a = str(a)
    x = 0
    for i in a:
        x += int(i)
    return x

for _ in range(0,t):
    x = input()
    n = int(x.split(' ')[0])
    d = int(x.split(' ')[1])
    
    dict = {n:0}
    stop_at = 1
    curr_items = [n]
    next_items = []
    steps = 0
    
    #if n%3 == 0 and d%3 == 0:
     #   stop_at = 3
    
    while stop_at not in dict and steps < 11:
        steps += 1
        for i in curr_items:
            ds = digisum(i) if i >= 10 else 0
            ad = i + d
            
            if ds != 0 and ds not in dict:
                next_items.append(ds)
                dict[ds] = steps
            
            if ad not in dict:
                next_items.append(ad)
                dict[ad] = steps
                
        curr_items,next_items = next_items,[] 
        
    for i in range(1,10):
        if i in dict:
            stop_at = i
            steps = dict[i]
            break
                
    print(stop_at,steps)
            


def digitSum(digit):
    result=0
    s=str(digit)
    for x in s:
        result+=int(x)
    return result

def main():
    t=int(input())
    for _ in range(t):
        l=[]
        min1, pos=100000, -10
        # f=[]
        # craw=[True, False, False, False, False, False, False, False, False, False]
        # dic={}
        # fag=[True]*10
        n, d=input().split(" ")
        n=int(n)
        d=int(d)

        i=0
        # if d%9==0:
        #     i=0
        #     while n>9:
        #         i+=1
        #         n=digitSum(n)
        #     print(n, i, sep=" ")
        # elif d%3==0:
        #     i=0
        #     while n>3:
        #         i+=1
        #         if n>9:
        #             n=digitSum(n)
        #         else:
        #             n+=d
        #     print(n, i, sep=" ")
        # else:
        l.append([n, 0])
        while i<10000 and l:
            tem=l.pop(0)
            if min1>tem[0]:
                min1=tem[0]
                pos=tem[1]
            if tem[0]>9:
                l.append([digitSum(tem[0]), tem[1]+1])
            l.append([tem[0]+d, tem[1]+1])
            i+=1
        print("{0} {1}".format(min1, pos))
main()


def digitSum(digit):
    result=0
    s=str(digit)
    for x in s:
        result+=int(x)
    return result

def main():
    t=int(input())
    for _ in range(t):
        l=[]
        min1, pos=100000, -10
        # f=[]
        # craw=[True, False, False, False, False, False, False, False, False, False]
        # dic={}
        # fag=[True]*10
        n, d=input().split(" ")
        n=int(n)
        d=int(d)

        i=0
        # if d%9==0:
        #     i=0
        #     while n>9:
        #         i+=1
        #         n=digitSum(n)
        #     print(n, i, sep=" ")
        # elif d%3==0:
        #     i=0
        #     while n>3:
        #         i+=1
        #         if n>9:
        #             n=digitSum(n)
        #         else:
        #             n+=d
        #     print(n, i, sep=" ")
        # else:
        l.append([n, 0])
        while i<100000 and l:
            tem=l.pop(0)
            if min1>tem[0]:
                min1=tem[0]
                pos=tem[1]
            if tem[0]>9:
                l.append([digitSum(tem[0]), tem[1]+1])
            l.append([tem[0]+d, tem[1]+1])
            i+=1
        print("{0} {1}".format(min1, pos))
main()

# cook your dish here
import queue
def digitsum(a):
    lo = 0
    s = str(a)
    for i in s:
        lo += int(i)
    return lo
for _ in range(int(input())):
    min1,pos = 1000000,-10
    track = queue.Queue(100000)
    n ,d = map(int,input().split())
    i = 0
    track.put([n,0])
    while i<100000 and track.empty()!=True:
        a,b = track.get()
        if min1>a:
            min1 = a
            pos = b
        if a>9:
            track.put([digitsum(a),b+1])
        track.put([a+d,b+1])
        i+=1
    print(min1,pos)

# -*- coding: utf-8 -*-
"""
Created on Tue Apr 23 17:13:53 2019

@author: avina
"""

def digit_sum(n):
    d= 0
    while n :
        d+= n%10
        n //= 10
    return d


for _ in range(int(input())):
    n,d = map(int, input().strip().split())

    q = []
    ma = {}
    q.append((n,0))
    i = 0
    while i < 10000 and len(q) != 0:
        t = q.pop(0)
        if t[0] < 10:
            if t[0] in ma:
                continue
            else:
                ma[t[0]] = t[1]
        else:
            q.append((digit_sum(t[0]) , t[1]+1))
    
        q.append((t[0] + d, t[1] + 1))
        i+=1
    k = sorted(list(ma.keys()))
    print(k[0], ma[k[0]])
    

def digitsum(n):
    s=0
    while n:
        s=s+n%10
        n=n//10
    return(s)
x=int(input())
for i in range(x):
    a,b=input().split()
    a,b=[int(a),int(b)]
    l1=[(a,0)]
    l2={}
    i=0
    while i<10000 and len(l1)!=0:
        first=l1.pop(0)
        if first[0]<10:
            if first[0] not in l2:
                l2[first[0]]=first[1]
        else:
            l1.append((digitsum(first[0]),first[1]+1))
        l1.append((first[0]+b,first[1]+1))
        i+=1
    a=min(l2)
    print(a,l2[a])

def digitsum(n):
    s=0
    while n:
        s=s+n%10
        n=n//10
    return(s)
x=int(input())
for i in range(x):
    a,b=input().split()
    a,b=[int(a),int(b)]
    l1=[(a,0)]
    l2={}
    i=0
    while i<10000 and len(l1)!=0:
        first=l1.pop(0)
        if first[0]<10:
            if first[0] not in l2:
                l2[first[0]]=first[1]
        else:
            l1.append((digitsum(first[0]),first[1]+1))
        l1.append((first[0]+b,first[1]+1))
        i+=1
    a=min(l2)
    print(a,l2[a])

# https://www.codechef.com/OCT18B/problems/MINDSUM
'''
	Author - Subhajit Das
	University of Engineering and Management, Kolkata
	28/1/2018
'''


def sum_digits(x):
    return sum(map(int, str(x)))


def main():
    for _ in range(int(input())):
        n, d = map(int, input().strip().split())

        que = [(n, 0)]
        min_track = dict()
        i = 0
        op_count = 0
        while len(que) != 0 and i <= 1000:
            i += 1
            n, op_count = que.pop(0)
            if n == 1:
                break
            if n > 1 and n <= 9:
                if n not in min_track.keys():
                    min_track[n] = op_count
                else:
                    min_track[n] = min(min_track[n], op_count)
            else:
                que.append((sum_digits(n), op_count+1))
            que.append((n+d, op_count+1))

        if n == 1:
            print(n, op_count)
        else:
            min_key = min(min_track.keys())
            print(min_key, min_track[min_key])


def __starting_point():
    main()

__starting_point()

# https://www.codechef.com/OCT18B/problems/MINDSUM
'''
	Author - Subhajit Das
	University of Engineering and Management, Kolkata
	28/1/2018
'''


def sum_digits(x):
    return sum(map(int, str(x)))


def main():
    for _ in range(int(input())):
        n, d = map(int, input().strip().split())

        que = [(n, 0)]
        min_track = dict()
        i = 0
        op_count = 0
        while len(que) != 0 and i <= 10000:
            i += 1
            n, op_count = que.pop(0)
            if n == 1:
                break
            if n > 1 and n <= 9:
                if n not in min_track.keys():
                    min_track[n] = op_count
                else:
                    min_track[n] = min(min_track[n], op_count)
            else:
                que.append((sum_digits(n), op_count+1))
            que.append((n+d, op_count+1))

        if n == 1:
            print(n, op_count)
        else:
            min_key = min(min_track.keys())
            print(min_key, min_track[min_key])


def __starting_point():
    main()

__starting_point()

def dsum(n):
    ddsum=0
    while(n!=0):
        a=int(n%10)
        ddsum=ddsum+a
        n=int(n/10)
    return ddsum   

for _ in range(0,int(input())):
    l=[]
    a,b=map(int,input().split())
    minval=1000000000
    val=a
    cnt=0
    inv=0
    l.append([])
    l[inv].append(val)
    l[inv].append(cnt)
    if(minval>val):
        minval=val
        fcnf=cnt
    for j in range(0,50000):
        q=l.pop(0)
        inv-=1
        l.append([])
        cnt=q[1]+1
        inv+=1
        l[inv].append(q[0]+b)
        l[inv].append(cnt)
        if(minval>(q[0]+b)):
            minval=(q[0]+b)
            fcnf=cnt
        #print(l)    
        if(q[0]>9):
            p=dsum(q[0])
            l.append([])
            inv+=1
            l[inv].append(p)
            l[inv].append(cnt)
            if(minval>p):
                minval=p
                fcnf=cnt
    print(minval,fcnf)            


                 
                    



def dsum(n):
    ddsum=0
    while(n!=0):
        a=int(n%10)
        ddsum=ddsum+a
        n=int(n/10)
    return ddsum   

for _ in range(0,int(input())):
    l=[]
    a,b=map(int,input().split())
    minval=1000000000
    val=a
    cnt=0
    inv=0
    l.append([])
    l[inv].append(val)
    l[inv].append(cnt)
    if(minval>val):
        minval=val
        fcnf=cnt
    for j in range(0,100000):
        q=l.pop(0)
        inv-=1
        l.append([])
        cnt=q[1]+1
        inv+=1
        l[inv].append(q[0]+b)
        l[inv].append(cnt)
        if(minval>(q[0]+b)):
            minval=(q[0]+b)
            fcnf=cnt
        #print(l)    
        if(q[0]>9):
            p=dsum(q[0])
            l.append([])
            inv+=1
            l[inv].append(p)
            l[inv].append(cnt)
            if(minval>p):
                minval=p
                fcnf=cnt
    print(minval,fcnf)            


                 
                    



def ds(x):
		ss=0
		x=str(x)
		l=len(x)
		for i in range(l):
			m=int(x[i])
			ss+=m
		return int(ss)
import queue as q
t=int(input())
while(t):
	t=t-1
	n,d=map(int,input().split())
	a={n:0}
	i=0
	arr=q.Queue(maxsize=100000000000000)
	arr.put((n,0))
	while(i<100000):
		x=arr.get()
		p1=ds(x[0])
		p2=x[0]+d
		if p1<10 and not(p1 in a):
			a[p1]=x[1]+1
		if p2<10 and not(p2 in a):
			a[p2]=x[1]+1
		arr.put((p1,x[1]+1))
		arr.put((p2,x[1]+1))
		i+=1
	nn=min(a)
	print(nn,a[nn])

def dsum(n):
    return sum(int(i) for i in str(n))
for _ in range(int(input())):
    n,d=map(int,input().split())
    q=[n]
    lev=0 
    res=[]
    vis={}
    dist={}
    dist[n]=0
    lev=0 
    res.append([n,0])
    while q:
        siz=len(q)
        lev+=1 
        for i in range(siz):
            t=q.pop(0)
            if t+d not in vis:
                vis[t+d]=1 
                res.append([t+d,lev])
                #print(t,t+d,lev)
                dist[t+d]=dist.get(t)+1
                q.append(t+d)
            if dsum(t) not in vis:
                vis[dsum(t)]=1 
                res.append([dsum(t),lev])
                #print(t,dsum(t),lev)
                dist[dsum(t)]=dist.get(t)+1 
                q.append(dsum(t))
                
        if lev==32:
            break 
    #print(res)
    res.sort(key=lambda x:x[0])
    #print(res)
    print(res[0][0],res[0][1])

tl=int(input())
def dsum(n):
    ddsum=0
    while(n!=0):
        a=int(n%10)
        ddsum=ddsum+a
        n=int(n/10)
    return ddsum    
while(tl>0):
    n,d = map(int,input().split(" "))
    i=0
    dic=dict()
    l=[(n,0)]
    while(i<10000 and len(l)!=0):
        t=l.pop(0)
        if(t[0]<10):
            if(t[0] not in dic):
                dic[t[0]]=t[1]
            else:
                continue
        else:
            l.append((dsum(t[0]),t[1]+1))
        l.append((t[0]+d,t[1]+1))
        i+=1
    a=min(dic)
    print(a,dic[a])
    tl=tl-1

tl=int(input())
def dsum(n):
    ddsum=0
    while(n!=0):
        a=int(n%10)
        ddsum=ddsum+a
        n=int(n/10)
    return ddsum    
while(tl>0):
    n,d = map(int,input().split(" "))
    i=0
    dic=dict()
    l=[(n,0)]
    while(i<100000 and len(l)!=0):
        t=l.pop(0)
        if(t[0]<10):
            if(t[0] not in dic):
                dic[t[0]]=t[1]
            else:
                continue
        else:
            l.append((dsum(t[0]),t[1]+1))
        l.append((t[0]+d,t[1]+1))
        i+=1
    a=min(dic)
    print(a,dic[a])
    tl=tl-1

tl=int(input())
def dsum(n):
    ddsum=0
    while(n!=0):
        a=int(n%10)
        ddsum=ddsum+a
        n=int(n/10)
    return ddsum    
while(tl>0):
    n,d = map(int,input().split(" "))
    i=0
    dic=dict()
    l=[(n,0)]
    while(i<1000 and len(l)!=0):
        t=l.pop(0)
        if(t[0]<10):
            if(t[0] not in dic):
                dic[t[0]]=t[1]
            else:
                continue
        else:
            l.append((dsum(t[0]),t[1]+1))
        l.append((t[0]+d,t[1]+1))
        i+=1
    a=min(dic)
    print(a,dic[a])
    tl=tl-1