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$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Complete search


Solutions:
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


T = int(input())

def digitsum(N):
	string = str(N)
	string = list(string)
	string = [int(i) for i in string]
	return sum(string)
for i in range(T):
	(N, D) = map(int, input().split())
	result = dict()
	count = 0
	result[count] = [N]
	results = [N]
	for j in range(1, 12):
		for k in result[j - 1]:
			if j not in result:
				result[j] = []
			result[j].append(digitsum(k))
			result[j].append(k + D)
			results.append(digitsum(k))
			results.append(k + D)
	value = min(results)
	for i in range(12):
		if value in result[i]:
			print(value, i)
			break


t = int(input())

def digitSum(a):
	s = str(a)
	out = a
	out1 = a
	count = 0
	while len(s) > 1:
		out = 0
		for i in range(len(s)):
			out += int(s[i])
		s = str(out)
		count += 1
		if count == 1:
			out1 = out
	return [out, out1, count]
for x in range(t):
	(n, d) = input().split()
	n = int(n)
	d = int(d)
	da = digitSum(n)[0]
	ans = 10
	for i in range(10):
		temp1 = digitSum(i * d)[0]
		temp = digitSum(da + temp1)[0]
		if temp < ans:
			ans = temp
	q = []
	ans11 = 0
	q.append((n, 1))
	while len(q) != 0:
		num = q[0][0]
		step = q[0][1]
		q.pop(0)
		if num is ans:
			ans11 = step - 1
			break
		q.append((num + d, step + 1))
		q.append((digitSum(num)[1], step + 1))
	print(ans, ans11)


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
	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)


t = int(input())

def digitSum(a):
	s = str(a)
	out = a
	count = 0
	while len(s) > 1:
		out = 0
		for i in range(len(s)):
			out += int(s[i])
		s = str(out)
		count += 1
	return [out, 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
for x in range(t):
	(n, d) = input().split()
	n = int(n)
	d = int(d)
	da = digitSum(n)[0]
	ans = 10
	for i in range(10):
		temp1 = digitSum(i * d)[0]
		temp = digitSum(da + temp1)[0]
		if temp < ans:
			ans = temp
			ind = i
	tot = n + ind * d
	c = digitSum(tot)[1]
	q = []
	ans11 = 0
	q.append((n, 1))
	while len(q) != 0:
		num = q[0][0]
		step = q[0][1]
		q.pop(0)
		if num is ans:
			ans11 = step - 1
			break
		q.append((num + d, step + 1))
		q.append((ds(num), step + 1))
	print(ans, ans11)


def dgs(num):
	ans = 0
	while num > 0:
		ans = ans + num % 10
		num = num // 10
	return ans

def time(n, d, val):
	present = []
	q = []
	number = (n, 0)
	q.append(number)
	while q:
		t = q.pop(0)
		if t[0] == val:
			return t[1]
		present.append(t[0])
		if t[0] + d == val or dgs(t[0]) == val:
			return t[1] + 1
		if t[0] + d not in present:
			number = (t[0] + d, t[1] + 1)
			q.append(number)
		if dgs(t[0]) not in present:
			number = (dgs(t[0]), t[1] + 1)
			q.append(number)
	return 0
for _ in range(int(input())):
	(n, d) = input().split()
	(n, d) = (int(n), int(d))
	vol = n
	least = 10
	arr = []
	while 1:
		flag = dgs(vol)
		while 1:
			if flag < 10:
				break
			flag = dgs(flag)
		if flag not in arr:
			arr.append(flag)
			if flag < least:
				least = flag
		else:
			print(least, ' ', time(n, d, least))
			break
		vol = vol + d
	del arr[:]


T = int(input())

def sum_digits(n):
	r = 0
	while n:
		(r, n) = (r + n % 10, n // 10)
	return r

def step_Dsum(n, val):
	if n < 10:
		return val
	val = val + 1
	val = step_Dsum(sum_digits(n), val)
	return val

def sum_Digit(n):
	if n % 9 != 0:
		return n % 9
	else:
		return 9

def find_Min(n, d):
	iter = 0
	dig_min = 10
	val = n
	for i in range(9):
		if dig_min > sum_Digit(val):
			dig_min = min(dig_min, sum_Digit(val))
			iter = i
		val = val + d
	return (dig_min, iter)
while T:
	(n, d) = map(int, input().split(' '))
	(dig_min, iter) = find_Min(n, d)
	steps = step_Dsum(n + d * iter, 0)
	for i in range(iter):
		test = n + i * d
		k = 0
		while test > 9:
			k = k + 1
			test = sum_digits(test)
			times_sum = (iter - i) * d
			new_sum = test + times_sum
			steps = min(steps, k + step_Dsum(new_sum, 0))
	print(dig_min, iter + steps)
	T = T - 1


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)])


t = int(input())
while t > 0:
	lo = input().split()
	n = int(lo[0])
	d = int(lo[1])
	k = []
	k.append([n, 0])
	i = 0
	point = 0
	re = dict()
	re[n] = 1
	minnum = n
	pos_height = 0
	while i <= 10000:
		i = i + 1
		try:
			pop_element = k[point][0]
			height = k[point][1]
		except:
			break
		temp = pop_element
		sod = 0
		while temp != 0:
			q = temp % 10
			sod = sod + q
			temp = temp // 10
		first = sod
		if minnum > first:
			if first == minnum:
				if height + 1 < pos_height:
					pos_height = height + 1
			else:
				minnum = first
				pos_height = height + 1
		second = pop_element + d
		if minnum > second:
			if second == minnum:
				if height + 1 < pos_height:
					pos_height = height + 1
			else:
				minnum = second
				pos_height = height + 1
		if second not in re:
			re[second] = 1
			k.append([second, height + 1])
		if first not in re:
			re[first] = 1
			k.append([first, height + 1])
		point = point + 1
	print(minnum, ' ', pos_height)
	t = t - 1


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)
	mn = 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 mn:
			ans = step - 1
			break
		q.append((num + d, step + 1))
		q.append((ds(num), step + 1))
	print(str(mn) + ' ' + str(ans))


def digitsum(n):
	result = 0
	while n != 0:
		result += n % 10
		n = n // 10
	return result

def digits_queue(n, d):
	q = [n]
	sd = {}
	ld = set()
	for i in range(20):
		new_q = []
		for num in q:
			if num < 10:
				if num in sd:
					continue
				sd[num] = i
				if len(sd) == 9:
					return sd
			else:
				if num in ld:
					continue
				ld.add(num)
			new_q = new_q + [digitsum(num), num + d]
		q = new_q
	return sd

def mindsum(n, d):
	num = digits_queue(n, d)
	n = min(num.keys())
	return (n, num[n])
t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	r = mindsum(n, d)
	print(r[0], r[1])


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)


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]])


import math
from math import ceil

def Sum(t):
	sum = 0
	while t > 0:
		sum += t % 10
		t = int(t / 10)
	return sum
t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	ans = 0
	temp = n
	f = [0] * 10
	while True:
		rem = temp % 9
		if f[rem] == 1:
			break
		f[rem] = 1
		temp = rem + d
	for j in range(1, 10):
		if f[j] == 1:
			ans = j
			break
	if n == ans:
		print(n, 0)
	else:
		arr = [0] * 10000
		arr[0] = 0
		arr[1] = n
		k = 1
		c = 1
		b = 1
		while b == 1:
			temp = 2 * k
			arr[temp] = arr[k] + d
			arr[temp + 1] = Sum(arr[k])
			c += 2
			if arr[temp] == ans or arr[temp + 1] == ans:
				b = 0
			k += 1
		step = int(ceil(math.log(c + 1, 2)) - 1)
		print(ans, step)


import math
from math import ceil

def Sum(x):
	X = str(x)
	summ = 0
	for _ in X:
		summ += int(_)
	return summ
for i in range(int(input())):
	(n, d) = map(int, input().split())
	ans = 0
	temp = n
	f = [0] * 10
	while True:
		rem = temp % 9
		if f[rem] == 1:
			break
		f[rem] = 1
		temp = rem + d
	for j in range(1, 10):
		if f[j] == 1:
			ans = j
			break
	if n == ans:
		print(n, 0)
	else:
		arr = [0] * 10000
		arr[0] = 0
		arr[1] = n
		k = 1
		c = 1
		b = 1
		while b == 1:
			temp = 2 * k
			arr[temp] = arr[k] + d
			arr[temp + 1] = Sum(arr[k])
			c += 2
			if arr[temp] == ans or arr[temp + 1] == ans:
				b = 0
			k += 1
		coun = int(ceil(math.log(c + 1, 2)) - 1)
		print(ans, coun)


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
		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)


from functools import reduce as rd
import operator as optr
import math
import itertools
inp = lambda : map(int, input().split())

def digitsum(n):
	val = 0
	while n > 0:
		val += n % 10
		n //= 10
	return val
for __ in range(int(input())):
	(n, d) = inp()
	visit = {}
	ans = {}
	visit[str(n)] = 1
	queue = []
	ans[str(n)] = 0
	queue.append(n)
	iteration = 0
	result = 99999999999
	while queue:
		iteration += 1
		front = queue.pop(0)
		result = min(result, front)
		if iteration > 1000:
			break
		first = front + d
		second = digitsum(front)
		check1 = str(first) in visit
		check2 = str(second) in visit
		if check1 == False:
			visit[str(first)] = 1
			ans[str(first)] = ans[str(front)] + 1
			queue.append(first)
		if check2 == False:
			visit[str(second)] = 1
			ans[str(second)] = ans[str(front)] + 1
			queue.append(second)
	print(result, ans[str(result)])


def digitsum(num):
	s = 0
	while num > 0:
		s += num % 10
		num = num // 10
	return s

def find_min(mov, n, d, i, min_ops):
	if n < mov:
		mov = n
		min_ops = 0
	if n == 1 or i >= 13:
		return (0, mov)
	(ops1, mov1) = find_min(mov, n + d, d, i + 1, min_ops)
	ops1 += 1
	if digitsum(n) != n:
		(ops2, mov2) = find_min(mov, digitsum(n), d, i + 1, min_ops)
		ops2 += 1
		if n == min(mov1, mov2):
			return (min_ops, mov)
		if mov1 < mov2:
			return (ops1, mov1)
		elif mov1 == mov2:
			return (min(ops1, ops2), mov1)
		else:
			return (ops2, mov2)
	else:
		if n == mov1:
			return (min_ops, mov)
		return (ops1, mov1)
t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	(mini, min_ob_val) = find_min(n, n, d, 0, 15)
	if mini >= 13:
		mini = 0
	print(min_ob_val, mini)


def finder(n, num, cnt, p, x):
	if num == p[0] and cnt < p[1]:
		p[1] = cnt
	if num < p[0]:
		p[0] = num
		p[1] = cnt
		if p[0] == 1:
			return p
	if cnt == 11:
		return
	finder(n + x, sod(n), cnt + 1, p, x)
	finder(num + x, sod(num), cnt + 1, p, x)

def sod(n):
	s = 0
	while n > 0:
		d = n % 10
		s += d
		n = n // 10
	return s
n = int(input())
for i in range(n):
	(a, x) = map(int, input().split())
	ans = [a, 0]
	finder(a + x, sod(ans[0]), 1, ans, x)
	print(ans[0], ans[1])


def snek1(s):
	while s > 9:
		s2 = str(s)
		s = [int(i) for i in list(s2)]
		s = sum(s)
	return s

def snek2(s):
	h = 0
	while s > 0:
		h += s % 10
		s //= 10
	return h
t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	c = 10
	for j in range(10):
		s = n + d * j
		u = snek1(s)
		if u < c:
			c = u
	q = [[n, 0]]
	x = {}
	while len(q) > 0:
		l = q.pop(0)
		if l[0] < 10:
			if x.get(l[0]) != None:
				continue
			x[l[0]] = l[1]
		else:
			q.append([snek2(l[0]), l[1] + 1])
		q.append([l[0] + d, l[1] + 1])
		if l[0] == c:
			break
	print(c, x[c])


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)


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])


import filecmp
import operator
import os
import sys
from collections import deque

def digitsum(digits):
	digit_sum = 0
	while digits > 0:
		curr = digits % 10
		digit_sum += curr
		digits = digits // 10
	return digit_sum
FILE_IO = True if os.getenv('FILE_TEST') is not None else False
if FILE_IO:
	input_stream = open('input_test.txt')
	sys.stdout = open('current_output.txt', 'w')
else:
	input_stream = sys.stdin
T = int(input_stream.readline())
for _ in range(T):
	(N, D) = map(int, input_stream.readline().split())
	queue = deque()
	queue.appendleft((N, 0))
	i = 0
	memo = {}
	while len(queue) > 0 and i < 100000:
		(curr_n, steps) = queue.pop()
		if curr_n < 10:
			if memo.get(curr_n, None) is None:
				memo[curr_n] = steps
				queue.appendleft((curr_n + D, steps + 1))
		else:
			queue.appendleft((curr_n + D, steps + 1))
			queue.appendleft((digitsum(curr_n), steps + 1))
		i += 1
	first_elem = sorted(memo.items(), key=operator.itemgetter(0))
	print(first_elem[0][0], first_elem[0][1])
if FILE_IO:
	assert filecmp.cmp('current_output.txt', 'expected_output.txt', shallow=False) == True


def digitsumof(n):
	s = 0
	while n > 0:
		r = n % 10
		s += r
		n = n // 10
	return s

def rec(n, digin, count, l, d):
	if digin == l[0] and count < l[1]:
		l[1] = count
	if digin < l[0]:
		l[0] = digin
		l[1] = count
		if l[0] == 1:
			return 1
	if count == 11:
		return
	rec(n + d, digitsumof(n), count + 1, l, d)
	rec(digin + d, digitsumof(digin), count + 1, l, d)
t = int(input())
for i in range(t):
	(a, d) = map(int, input().split())
	l = [a, 0]
	rec(a + d, digitsumof(l[0]), 1, l, d)
	print(l[0], l[1])


import math

def step1(a, b):
	return a + b

def step2(a):
	s = 0
	while a:
		s += a % 10
		a //= 10
	return s
for t in range(int(input())):
	(n, d) = map(int, input().split())
	m = 0
	x = n
	f = [0] * 10
	while True:
		r = x % 9
		if f[r] == 1:
			break
		f[r] = 1
		x = step1(r, d)
	for j in range(1, 10):
		if f[j] == 1:
			m = j
			break
	if m == n:
		print(n, 0)
	else:
		a = [0] * 10000
		a[1] = n
		c = 1
		k = 1
		while True:
			x = 2 * k
			a[x] = step1(a[k], d)
			a[x + 1] = step2(a[k])
			c += 2
			if a[x] == m or a[x + 1] == m:
				break
			k += 1
		i = math.ceil(math.log(c + 1, 2)) - 1
		print(m, i)


def digit_sum(n):
	d_sum = 0
	while n != 0:
		d_sum += n % 10
		n = n // 10
	return d_sum

def recur(n, m, step_count=0):
	if n > 100000000000:
		return
	if step_count <= 10:
		recur(n + m, m, step_count + 1)
		recur(digit_sum(n), m, step_count + 1)
	d[n] = min(step_count, d.get(n, 10000))
ans = []
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	d = dict()
	recur(a, b)
	min_key = min(d.keys())
	ans.append(min_key)
	ans.append(d.get(min_key))
for i in range(0, len(ans), 2):
	print(ans[i], ans[i + 1])


def digit_sum(n, counter):
	n = str(n)
	ans = n
	while len(n) != 1:
		ans = 0
		for i in n:
			ans += int(i)
		n = str(ans)
		counter += 1
	return (int(ans), counter)

def summ(n):
	n = str(n)
	ans = 0
	for i in n:
		ans += int(i)
	return ans
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	arr = [0] * 20
	arr[0] = n
	for i in range(1, 20):
		arr[i] += arr[i - 1] + d
	brr = [summ(i) + d for i in arr]
	crr = [summ(i) + d * 2 for i in arr]
	drr = [summ(i) + d * 3 for i in arr]
	err = [summ(i) + d * 4 for i in arr]
	frr = [summ(i) + d * 5 for i in arr]
	dic = {1: 999, 2: 999, 3: 999, 4: 999, 5: 999, 6: 999, 7: 999, 8: 999, 9: 999}
	dic2 = {1: 999, 2: 999, 3: 999, 4: 999, 5: 999, 6: 999, 7: 999, 8: 999, 9: 999}
	dic3 = {1: 999, 2: 999, 3: 999, 4: 999, 5: 999, 6: 999, 7: 999, 8: 999, 9: 999}
	dic4 = {1: 999, 2: 999, 3: 999, 4: 999, 5: 999, 6: 999, 7: 999, 8: 999, 9: 999}
	dic5 = {1: 999, 2: 999, 3: 999, 4: 999, 5: 999, 6: 999, 7: 999, 8: 999, 9: 999}
	dic6 = {1: 999, 2: 999, 3: 999, 4: 999, 5: 999, 6: 999, 7: 999, 8: 999, 9: 999}
	for i in range(len(arr)):
		(ans, counter) = digit_sum(arr[i], i)
		dic[ans] = min(dic[ans], counter)
	for i in range(len(brr)):
		(ans, counter) = digit_sum(brr[i], i + 2)
		dic2[ans] = min(dic2[ans], counter)
	for i in range(len(crr)):
		(ans, counter) = digit_sum(crr[i], i + 2 + 1)
		dic3[ans] = min(dic3[ans], counter)
	for i in range(len(drr)):
		(ans, counter) = digit_sum(drr[i], i + 2 + 2)
		dic4[ans] = min(dic4[ans], counter)
	for i in range(len(err)):
		(ans, counter) = digit_sum(err[i], i + 2 + 3)
		dic5[ans] = min(dic5[ans], counter)
	for i in range(len(frr)):
		(ans, counter) = digit_sum(frr[i], i + 2 + 4)
		dic6[ans] = min(dic6[ans], counter)
	b = list(dic.items())
	b.sort()
	b2 = list(dic2.items())
	b2.sort()
	b3 = list(dic3.items())
	b3.sort()
	b4 = list(dic4.items())
	b4.sort()
	b5 = list(dic5.items())
	b5.sort()
	b6 = list(dic6.items())
	b6.sort()
	for i in range(len(b)):
		if b[i][1] != 999 and b2[i][1] != 999 and (b3[i][1] != 999):
			print(b[i][0], min([b[i][1], b2[i][1], b3[i][1], b4[i][1], b5[i][1], b6[i][1]]))
			break


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()


def digitSum(entier):
	return sum([int(i) for i in str(entier)])

def CountToLesser(entier):
	count = 0
	while entier > 9:
		entier = digitSum(entier)
		count += 1
	return count

def toLesser(entier):
	l = entier % 9
	return l if l > 0 or entier == 0 else 9

def findMin(n, d):
	a = []
	for i in range(9):
		a.append((toLesser(n + i * d), i))
	return min(a)

def CountToLesser(N, D, i, res):
	poss = [(N, 0, 0)]
	index = 0
	while True:
		(n, k, c) = poss[index]
		if n == res:
			return c
		if k < i:
			poss.append((n + D, k + 1, c + 1))
		poss.append((digitSum(n), k, c + 1))
		index += 1
T = int(input())
for i in range(T):
	(N, D) = [int(i) for i in input().split()]
	n = toLesser(N)
	d = toLesser(D)
	(res, i) = findMin(n, d)
	total = N + i * D
	count = CountToLesser(N, D, i, res)
	print(res, count)


import sys
sys.setrecursionlimit(1000000000)

def digitsum(n):
	summer = 0
	while n != 0:
		summer = summer + n % 10
		n = n // 10
	return summer

def everyonesfaveloli(a, b, st):
	if st > 100:
		return
	try:
		drx = ar[a]
		if ar[a] < st:
			return
	except:
		t = 0
	ar[a] = st
	if a < 10 and ans[a] < st:
		return
	elif a < 10:
		ans[a] = st
	if a > n + d * 10:
		return
	x = digitsum(a)
	y = a + b
	if x == a:
		everyonesfaveloli(y, b, st + 1)
	elif y > n + d * 10:
		everyonesfaveloli(x, b, st + 1)
	else:
		everyonesfaveloli(y, b, st + 1)
		everyonesfaveloli(x, b, st + 1)
for imh in range(int(input())):
	(n, d) = list(map(int, input().split()))
	l = [-1] * 10
	jk = n + 10 * d
	x = n
	y = n
	if n < 10:
		l[n] = 0
	if n == 1:
		print(1, 0)
	else:
		ar = {}
		ans = {0: 1000, 1: 1000, 2: 1000, 3: 1000, 4: 1000, 5: 1000, 6: 1000, 7: 1000, 8: 1000, 9: 1000, 10: 1000}
		everyonesfaveloli(n, d, 0)
		for key in ans.keys():
			if ans[key] != 1000:
				print(key, ans[key])
				break


def digisum(n):
	ans = 0
	while n != 0:
		dig = n % 10
		ans += dig
		n //= 10
	return ans

def findmin(n, d):
	min = n
	for i in range(200):
		if n < min:
			min = n
		if n >= 10:
			n = digisum(n)
		else:
			n += d
	return min
for i in range(int(input())):
	(n, d) = map(int, input().split())
	m = findmin(n, d)
	if n == m:
		print('%d 0' % m)
		continue
	else:
		oldlist = [n]
		newlist = [n]
		steps = 0
		done = False
		while done != True:
			steps += 1
			oldlist = newlist
			newlist = []
			for j in range(len(oldlist)):
				newlist.append(oldlist[j] + d)
				newlist.append(digisum(oldlist[j]))
				if newlist[2 * j] == m or newlist[2 * j + 1] == m:
					print('%d %d' % (m, steps))
					done = True
					break


import sys
sys.setrecursionlimit(1000000)

def digitsum(x, d, ct):
	if ct > 11:
		return
	l.append([x, ct])
	if x > 9:
		a = sum(map(int, list(str(x))))
		digitsum(a, d, ct + 1)
	digitsum(x + d, d, ct + 1)
t = int(input())
while t:
	t -= 1
	(n, d) = map(int, input().strip().split())
	l = []
	digitsum(n, d, 0)
	l.sort()
	print(l[0][0], l[0][1])


from sys import stdin, stdout
input = stdin.readline

def digitSum1(n):
	while n > 9:
		num = str(n)
		n = list(num)
		n = [int(digit) for digit in n]
		n = sum(n)
	return n

def digitSum2(n):
	total = 0
	while n > 0:
		total += n % 10
		n //= 10
	return total
t = int(input().strip())
for _ in range(t):
	(n, d) = list(map(int, input().strip().split()))
	mini = 10
	for i in range(10):
		num = n + d * i
		digit_sum = digitSum1(num)
		if digit_sum < mini:
			mini = digit_sum
	que = [[n, 0]]
	d1 = dict()
	while len(que) > 0:
		ele = que.pop(0)
		if ele[0] < 10:
			if d1.get(ele[0]) != None:
				continue
			d1[ele[0]] = ele[1]
		else:
			que.append([digitSum2(ele[0]), ele[1] + 1])
		que.append([ele[0] + d, ele[1] + 1])
		if ele[0] == mini:
			break
	print(mini, d1[mini])


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 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])


import math

def sum_digits(number):
	return sum((int(digit) for digit in str(number)))
t = int(input())
for _ in range(t):
	(n, d) = [int(n) for n in input().split()]
	arr = [n] * 4098
	arr[0] = n
	index = 1
	i = 0
	while i < 2049:
		arr[2 * i + 1] = arr[i] + d
		arr[2 * i + 2] = sum_digits(arr[i])
		i += 1
		if i == 2048:
			break
	minimum = n
	for i in range(4098):
		if arr[i] < minimum:
			minimum = arr[i]
			index = i
	print(minimum, int(math.log(index, 2)))


import math
temp = int(input())
while temp > 0:
	(num, d) = map(int, input().split())

	def sumdig(num):
		s = 0
		while num:
			s += num % 10
			num //= 10
		return s
	a = [None] * 20005
	p = 0
	min = num
	for i in range(10000):
		if 2 * i + 2 < 20005:
			a[0] = num
			f = sumdig(a[i])
			a[2 * i + 1] = f
			a[2 * i + 2] = a[i] + d
			if min > a[2 * i + 1]:
				min = a[2 * i + 1]
	p = a.index(min) + 1
	if p == 0:
		b = 0
	else:
		b = math.floor(math.log2(p))
	print(min, b)
	temp = temp - 1


def DigitSum(N):
	sum = 0
	while N > 0:
		sum += N % 10
		N = int(N / 10)
	return sum

def minimizeDigitsum(N, D, countOperations):
	digitSum = DigitSum(N)
	if countOperations > 10:
		return
	countOperations += 1
	if N < 10:
		if visited[N] == 1:
			if operations[N] <= countOperations:
				return
		visited[N] = 1
		operations[N] = countOperations
	minimizeDigitsum(N + D, D, countOperations)
	minimizeDigitsum(digitSum, D, countOperations)
	return
visited = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
operations = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
tc = int(input())
while tc:
	countOperations = -1
	(N, D) = map(int, input().split())
	minimizeDigitsum(N, D, countOperations)
	for i in range(1, 10):
		if visited[i] == 1:
			print(i, operations[i])
			break
	for i in range(1, 10):
		visited[i] = 0
	tc -= 1


def getsum(n):
	s = 0
	while n > 0:
		d = n % 10
		s += d
		n = n // 10
	return s

def tsm(n, m, c, a, l):
	if c <= 12:
		x = n + m
		y = getsum(n)
		a.append([x, c])
		a.append([y, c])
		l.append(x)
		l.append(y)
		tsm(x, m, c + 1, a, l)
		tsm(y, m, c + 1, a, l)
	else:
		return
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	c = 0
	a = []
	h = 0
	l = []
	x = tsm(n, m, c, a, l)
	d = min(l)
	if d == n:
		print(d, 0)
	elif d == getsum(n):
		print(d, 1)
	else:
		p = []
		for i in range(len(a)):
			if a[i][0] == d:
				p.append(a[i][1])
		print(d, min(p) + 1)


def digitsum(num):
	sums = 0
	while num != 0:
		sums += num % 10
		num = num // 10
	return sums

def add_op(cnt, arr, d, k):
	arr[cnt * 2 + 2] = k + d
	arr[cnt * 2 + 1] = digitsum(k)
t = int(input())
for loop in range(t):
	(n, d) = map(int, input().split())
	cnt = 0
	arr = [9] * 10000
	arr[0] = n
	while cnt < 4097:
		add_op(cnt, arr, d, arr[cnt])
		cnt += 1
	min_i = arr.index(min(arr))
	min_v = min(arr)
	c = 0
	while min_i != 0:
		if min_i % 2 == 0:
			min_i = (min_i - 2) // 2
		else:
			min_i = (min_i - 1) // 2
		c += 1
	print(min_v, c)


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
		elif 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 T(N):
	A = str(N)
	n = len(A)
	y = 0
	while n != 1:
		x = 0
		for j in A:
			x += int(j)
		A = str(x)
		n = len(A)
		y += 1
	return (int(A), y)

def U(N):
	B = str(N)
	x = 0
	for j in B:
		x += int(j)
	return x
a = int(input())
for i in range(a):
	(N, D) = map(int, input().split())
	p = T(N)
	q = T(D)
	ans = [0, 0]
	if q[0] == 9:
		ans[0] = p[0]
		if p[1] <= T(N + D)[1] + 1:
			ans[1] = p[1]
		else:
			ans[1] = T(N + D)[1] + 1
	elif q[0] == 6:
		a = min(p[0], T(p[0] + 6)[0], T(p[0] + 3)[0])
		ans[0] = a
		if a == p[0]:
			ans[1] = p[1]
		elif a == T(p[0] + 6)[0]:
			ans[1] = min(T(U(N) + D)[1] + 2, T(N + D)[1] + 1)
		else:
			ans[1] = min(T(U(N) + 2 * D)[1] + 3, T(U(N + D) + D)[1] + 3, T(N + 2 * D)[1] + 2)
	elif q[0] == 3:
		a = min(p[0], T(p[0] + 6)[0], T(p[0] + 3)[0])
		ans[0] = a
		if a == p[0]:
			ans[1] = p[1]
		elif a == T(p[0] + 3)[0]:
			ans[1] = min(T(U(N) + D)[1] + 2, T(N + D)[1] + 1)
		else:
			ans[1] = min(T(U(N) + 2 * D)[1] + 3, T(U(N + D) + D)[1] + 3, T(N + 2 * D)[1] + 2)
	else:
		g = 0
		ans[0] = 1
		A = N
		for j in range(20):
			if T(A)[0] == 1:
				break
			else:
				A = A + D
				g += 1
		ans[1] = T(N + g * D)[1] + g
		for j in range(0, g + 1):
			if T(U(N + j * D) + (g - j) * D)[1] + g + 1 < ans[1]:
				ans[1] = T(U(N + j * D) + (g - j) * D)[1] + g + 1
	print(ans[0], ans[1])


def digit_sum(n):
	d_sum = 0
	while n != 0:
		d_sum += n % 10
		n = n // 10
	return d_sum
ans = []
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	d = dict()
	val_arr = [a]
	d[a] = 0
	steps_count = 0
	l_index = 1
	while steps_count <= 10:
		for counter in range(steps_count, l_index):
			val = val_arr[counter]
			if val > 100000000000:
				break
			d_sum = digit_sum(val)
			d[d_sum] = min(steps_count + 1, d.get(d_sum, 10000))
			val_arr.append(d_sum)
			l_index += 1
			val_b = val + b
			d[val_b] = min(steps_count + 1, d.get(val_b, 10000))
			val_arr.append(val_b)
			l_index += 1
		steps_count += 1
	min_key = min(d.keys())
	ans.append(min_key)
	ans.append(d.get(min_key))
for i in range(0, len(ans), 2):
	print(ans[i], ans[i + 1])


for case in range(int(input())):
	(n, d) = (int(i) for i in input().split())
	steps = 0
	if d % 9 == 0:
		ans = n % 9
		if ans == 0:
			ans = 9
	elif d % 3 == 0:
		ans = n % 3
		if ans == 0:
			ans = 3
	else:
		ans = 1
	if n == ans:
		print(ans, steps)
		continue
	ops = [n]
	while ans not in ops:
		steps += 1
		temp = []
		for i in ops:
			if i + d not in ops:
				temp.append(i + d)
			ds = sum((int(_) for _ in str(i)))
			if ds not in ops:
				temp.append(ds)
		ops = temp
	print(ans, steps)


import math

def Two(n):
	if n == 0:
		return 0
	while n != 1:
		if n % 2 != 0:
			return 1
		n = n // 2
	return 1

def sum1(n):
	total = 0
	while n > 0:
		digit = n % 10
		total = total + digit
		n = n // 10
	return total
a = int(input())
for i in range(a):
	b = [int(i) for i in input().split()]
	c = []
	d = []
	g = []
	g = [0] * 11
	for i in range(11):
		c.append(b[0] + i * b[1])
	for i in range(11):
		d.append(i)
	for i in range(len(c)):
		l = 0
		k = c[i]
		r = 0
		while k // 10 != 0:
			k = sum1(k)
			l = l + 1
		d[i] = d[i] + l
		g[i] = k
	t = g.index(min(g))
	outf2 = min(g)
	e = d[t]
	f = [0] * (2 ** (e + 1) - 1)
	f[0] = b[0]
	for i in range(len(f) - 2 ** e):
		f[2 * i + 1] = f[i] + b[1]
		f[2 * i + 2] = sum1(f[i])
	for out1 in range(len(f)):
		if f[out1] == outf2:
			break
	if Two(out1 + 1):
		outf = math.log(out1 + 1, 2)
	else:
		outf = math.log(out1, 2)
	print(outf2, end=' ')
	print(math.floor(outf))


from queue import Queue

def Sum(n):
	dig_sum = n
	first_sum = n
	sum_count = 0
	while dig_sum > 9:
		temp = dig_sum
		dig_sum = 0
		sum_count += 1
		while temp > 0:
			dig_sum += temp % 10
			temp = temp // 10
		if sum_count == 1:
			first_sum = dig_sum
	return [first_sum, dig_sum, sum_count]

def SingleSum(n):
	dig_sum = 0
	while n > 0:
		dig_sum += n % 10
		n = n // 10
	return dig_sum

def SearchMin(qu, D, min_val):
	[level, value] = qu.get()
	if value <= min_val:
		return [True, min_val, level]
	if value > 9:
		left_val = SingleSum(value)
		qu.put([level + 1, left_val])
	right_value = value + D
	qu.put([level + 1, right_value])
	return [False, 0, 0]
max_tree = [0, 0, 0]

def FindMinimized(N, D):
	global max_tree
	if D % 9 == 0:
		if N % 9 == 0:
			min_val = 9
		else:
			min_val = N % 9
	elif D % 3 == 0:
		if N % 3 == 0:
			min_val = 3
		else:
			min_val = N % 3
	else:
		min_val = 1
	qu = Queue()
	qu.put([0, N])
	res = False
	count = 0
	while res == False:
		(res, min_val_ret, count) = SearchMin(qu, D, min_val)
	print(str(min_val_ret) + ' ' + str(count))

def FindMinimized20(N, D, min_val):
	qu = Queue()
	qu.put([0, N])
	res = False
	count = 0
	iteration = 2 ** 20
	while (res == False) & (iteration > 0):
		iteration -= 1
		(res, min_val_ret, count) = SearchMin(qu, D, min_val)
	return [min_val_ret, count]
t = int(input())
for i in range(t):
	(N, D) = map(int, input().split())
	FindMinimized(N, D)


def helper(n, d, k):
	if k == 0:
		if n < 10:
			return 0
		else:
			return 1 + helper(sum(list(map(int, list(str(n))))), d, 0)
	elif n < 10:
		return 1 + helper(n + d, d, k - 1)
	else:
		return 1 + min(helper(sum(list(map(int, list(str(n))))), d, k), helper(n + d, d, k - 1))
for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	rem = [(a + i * b) % 9 for i in range(9)]
	lis = sorted(list(set(rem)))
	if lis[0] == 0:
		if len(lis) == 1:
			mini = 0
			ans = 9
		else:
			mini = rem.index(lis[1])
			ans = lis[1]
	else:
		mini = rem.index(lis[0])
		ans = lis[0]
	print(ans, helper(a, b, mini))


def digitsum(N):
	_sum = 0
	while N:
		_sum += N % 10
		N //= 10
	return _sum
for _ in range(int(input())):
	(N, D) = map(int, input().split())
	if not D % 9:
		goal = N % 9
		if not goal:
			goal = 9
	elif not D % 3:
		goal = N % 3
		if not goal:
			goal = 3
	else:
		goal = 1
	values = {N}
	steps = 0
	while goal not in values:
		prev_values = values
		values = set()
		for x in prev_values:
			values.add(x + D)
			values.add(digitsum(x))
		steps += 1
	print(goal, steps)


def digitSum(a):
	q = a
	sum = 0
	while q != 0:
		r = q % 10
		q = q // 10
		sum += r
	return sum
import queue
t = int(input())
for a0 in range(t):
	(n, d) = [int(x) for x in input().split()]
	arr = [-1] * 10
	q1 = queue.Queue()
	q2 = queue.Queue()
	count = 1
	if n // 10 == 0:
		arr[n] = 0
	q1.put([n, 0])
	q2.put([n, 0])
	while not q1.empty() or not q2.empty():
		if not q1.empty():
			a1 = q1.get()
			ds = digitSum(a1[0])
			if ds // 10 == 0 and arr[ds] == -1:
				arr[ds] = a1[1] + 1
				q2.put([ds, a1[1] + 1])
			if ds // 10 != 0:
				q1.put([ds, a1[1] + 1])
				q2.put([ds, a1[1] + 1])
		if not q2.empty():
			a2 = q2.get()
			sum = a2[0] + d
			if sum // 10 == 0 and arr[sum] == -1:
				arr[sum] = a2[1] + 1
				q2.put([sum, a2[1] + 1])
			if sum // 10 != 0:
				q1.put([sum, a2[1] + 1])
				q2.put([sum, a2[1] + 1])
		count += 1
		if count > 10000:
			break
	for i in range(10):
		if arr[i] != -1:
			print(i, arr[i])
			break


from queue import Queue

def Sum(n):
	dig_sum = n
	initial = n
	sum_count = 0
	while dig_sum > 9:
		temp = dig_sum
		dig_sum = 0
		sum_count += 1
		while temp > 0:
			dig_sum += temp % 10
			temp = temp // 10
		if sum_count == 1:
			initial = dig_sum
	return [initial, dig_sum, sum_count]

def digit(n):
	dig_sum = 0
	while n > 0:
		dig_sum += n % 10
		n = n // 10
	return dig_sum

def obtain_min(queue, D, min_val):
	[level, data] = queue.get()
	if data <= min_val:
		return [True, min_val, level]
	if data > 9:
		left_node = digit(data)
		queue.put([level + 1, left_node])
	right_node = data + D
	queue.put([level + 1, right_node])
	return [False, 0, 0]

def min(N, D):
	result = False
	count = 0
	if D % 9 == 0:
		if N % 9 == 0:
			min_val = 9
		else:
			min_val = N % 9
	elif D % 3 == 0:
		if N % 3 == 0:
			min_val = 3
		else:
			min_val = N % 3
	else:
		min_val = 1
	queue = Queue()
	queue.put([0, N])
	while result != True:
		(result, min_val_ret, count) = obtain_min(queue, D, min_val)
	print(str(min_val_ret) + ' ' + str(count))
test_case = int(input())
for i in range(test_case):
	(n, d) = map(int, input().split())
	min(n, d)


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)
		(n, d) = input().split(' ')
		n = int(n)
		d = int(d)
		i = 0
		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()


def digitsum(n2):
	rr = 0
	while n2 >= 10:
		x = 0
		while n2 != 0:
			x = x + n2 % 10
			n2 = n2 // 10
		rr = rr + 1
		if x <= 9:
			break
		n2 = x
	return rr
t = int(input())
while t > 0:
	t = t - 1
	(n, d) = map(int, input().split(' '))
	a = n % 9
	b = d % 9
	if a == 0:
		a = 9
	if b == 0:
		b = 9
	m = a
	i = 1
	r = 0
	while i < 10:
		a = a + b
		a = a % 9
		if a == 0:
			a = 9
		if a < m:
			r = i
			m = a
		i = i + 1
	n1 = n + r * d
	r1 = digitsum(n1)
	r2 = r1
	n1 = n + (r + 1) * d
	a1 = n1 % 9
	if a1 == 0:
		a1 = 9
	if a1 == m:
		r2 = 1 + digitsum(n1)
	r1 = min(r1, r2)
	if r1 == 3:
		i = r
		n11 = n + i * d
		while i >= 0:
			n1 = n + i * d
			n10 = n1
			x = 0
			while n10 != 0:
				x = x + n10 % 10
				n10 = n10 // 10
			n1 = n11 - n1 + x
			if digitsum(n1) == 1:
				r1 = 2
				break
			i = i - 1
	r = r + r1
	print(m, r)


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])
				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])
				dist[dsum(t)] = dist.get(t) + 1
				q.append(dsum(t))
		if lev == 32:
			break
	res.sort(key=lambda x: x[0])
	print(res[0][0], res[0][1])


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
from collections import deque

def digitsum(val):
	res = 0
	while val > 0:
		res += val % 10
		val //= 10
	return res

def stepToTarget(n, d, target):
	q = deque([(n, 0)])
	visited = {n}
	maxStep = 1000
	while q:
		(v, s) = q.popleft()
		if v == target:
			return s
		for u in [v + d, digitsum(v)]:
			if u not in visited:
				visited.add(u)
				q.append((u, s + 1))
		if s > maxStep:
			return -1
	return -1

def solve(n, d):
	for target in range(10):
		step = stepToTarget(n, d, target)
		if step >= 0:
			return ' '.join(map(str, [target, step]))
T = int(input())
for ti in range(T):
	(N, D) = map(int, input().split())
	print(solve(N, D))


import sys

def digsum(n):
	n = sum((int(digit) for digit in str(n)))
	return n

def testing(N, D):
	save = {}
	q = []
	q.append((N, 0))
	i = 0
	minn = N
	minop = 0
	save[N] = 0
	while i < 10000 and len(q) > 0:
		(n, op) = q.pop()
		if n < 10:
			if n not in save:
				save[n] = op
		else:
			q.insert(0, (digsum(n), op + 1))
		q.insert(0, (n + D, op + 1))
		i += 1
	s = min(save.keys())
	print(s, save[s])

def main():
	t = int(input())
	I = {}
	for i in range(t):
		(N, D) = [int(item) for item in input().split()]
		I[i] = [N, D]
	for (k, v) in I.items():
		(N, D) = v
		testing(N, D)
	return 0
main()


def sum1(a, d):
	return a + d

def dsum(n):
	total = 0
	while n != 0:
		total += n % 10
		n = n // 10
	return total

def mn(n, d):
	t1 = [0 for k in range(10)]
	m = sum1(n, d)
	while t1.count(0) != 0:
		if t1[1] == 1:
			return 1
		while len(str(m)) > 1:
			m = dsum(m)
		if t1[m] == 0:
			t1[m] = 1
		else:
			break
		m = sum1(m, d)
	return t1.index(1)
t = int(input())
for l1 in range(t):
	l = [int(y) for y in input().split()]
	n = l[0]
	d = l[1]
	if n == 1:
		print(str(1) + ' ' + str(0))
		continue
	minm = mn(n, d)
	if minm == n:
		print(str(n) + ' ' + str(0))
		continue
	temp = []
	temp.append([n, 0])
	temp1 = []
	temp1.append(n)
	for j in temp:
		l1 = sum1(j[0], d)
		l2 = dsum(j[0])
		if l1 not in temp1:
			temp.append([l1, j[1] + 1])
			temp1.append(l1)
		if l2 not in temp1:
			temp.append([l2, j[1] + 1])
			temp1.append(l2)
		if min(temp1) == minm:
			break
	for j in temp:
		if j[0] == minm:
			print(str(minm) + ' ' + str(j[1]))
			break


def sumof(n):
	s = 0
	while n > 0:
		r = n % 10
		s += r
		n = n // 10
	return s

def recu(n, digi_n, c, l, d):
	if digi_n == l[0] and c < l[1]:
		l[1] = c
	if digi_n < l[0]:
		l[0] = digi_n
		l[1] = c
		if l[0] == 1:
			return l
	if c == 11:
		return
	recu(n + d, sumof(n), c + 1, l, d)
	recu(digi_n + d, sumof(digi_n), c + 1, l, d)
n = int(input())
for i in range(n):
	(x, d) = [int(i) for i in input().split()]
	l = [x, 0]
	recu(x + d, sumof(l[0]), 1, l, d)
	print(l[0], l[1])


import sys
sys.setrecursionlimit(1000000000)

def summ(n):
	c = 0
	while n >= 10:
		c += 1
		n = digsum(n)
	return (c, n)

def digsum(n):
	s = 0
	while n != 0:
		s = s + n % 10
		n = n // 10
	return s

def answer(n, sp):
	print(l, n, sp)
	if n < 10 and l[n] <= sp and (l[n] != -1):
		return
	x = digsum(n)
	y = n + d
	f = 0
	if x >= 10 and x != n:
		answer(x, sp + 1)
	if x < 10 and x != n:
		if l[x] == -1:
			l[x] = sp + 1
		elif l[x] > sp:
			l[x] = sp + 1
		else:
			f = 1
			return
	if y >= 10:
		answer(y, sp + 1)
	if y < 10:
		if l[y] == -1:
			l[y] = sp + 1
			answer(y, sp + 1)
		elif l[y] > sp:
			l[y] = sp + 1

def reanswer(n, sp):
	print(l, n, sp)
	if n < 10 and l[n] <= sp:
		return
	x = digsum(n)
	y = n + d
	if x < 10:
		if l[x] == -1 or l[x] > sp:
			if n != x:
				l[x] = sp + 1
			if x != -1:
				reanswer(x, sp + 1)
		else:
			return
	if x >= 10:
		reanswer(x, sp + 1)
	print('HHH')
	if y < 10:
		if l[y] == -1 or l[y] > sp:
			l[y] = sp + 1
			reanswer(y, sp + 1)
		else:
			return
	if y >= 10:
		reanswer(y, sp + 1)

def ans(n, sp):
	if n < 10 and l[n] < sp and (l[n] > 0):
		return
	x = digsum(n)
	y = n + d
	print(l, n, sp, x, y)
	if x < 10:
		if l[x] < 0 or l[x] > sp:
			if x == n:
				l[x] = sp
			else:
				l[x] = sp + 1
	if x >= 10:
		ans(x, sp + 1)
	if y < 10:
		if l[y] == -1 or l[y] > sp:
			l[y] = sp + 1
			ans(y, sp + 1)
		else:
			return
	if y >= 10 and y <= jk:
		ans(y, sp + 1)

def lol(n, sp):
	x = digsum(n)
	y = n + d
	print(l, n, sp, x, y, dic)
	f1 = 0
	f2 = 0
	try:
		my = dic[x]
		if my < sp:
			f1 = 1
	except:
		dic[x] = sp
	try:
		my = dic[y]
		if my < sp:
			f2 = 1
	except:
		dic[y] = sp
	if f1 == 0:
		if x < 10:
			if (l[x] == -1 or l[x] > sp) and x != n:
				l[x] = sp + 1
				lol(x, sp + 1)
		if x >= 10:
			lol(x, sp + 1)
	if f2 == 0:
		if y < 10:
			if l[y] == -1 or l[y] > sp:
				l[y] = sp + 1
				lol(y, sp + 1)
		if y >= 10:
			lol(y, sp + 1)

def lol2(a, b, sp):
	if a > n + 10 * d:
		return
	if a < 10 and (dans[a] == 1000 or dans[a] < sp):
		dans[a] = sp
		return lol2(a + b, b, sp + 1)
	if a >= 10:
		return lol2(a + b, b, sp + 1)
		return lol2(digsum(a), b, sp + 1)

def l3(a, b, sp):
	if sp > 100:
		return
	try:
		drx = ar[a]
		if ar[a] < sp:
			return
	except:
		ty = 10
	ar[a] = sp
	if a < 10 and dans[a] < sp:
		return
	elif a < 10:
		dans[a] = sp
	if a > n + d * 10:
		return
	x = digsum(a)
	y = a + b
	if x == a:
		l3(y, b, sp + 1)
	elif y > n + d * 10:
		l3(x, b, sp + 1)
	else:
		l3(y, b, sp + 1)
		l3(x, b, sp + 1)
for imh in range(int(input())):
	dic = {}
	(n, d) = list(map(int, input().split()))
	l = [-1] * 10
	jk = n + 10 * d
	x = n
	y = n
	if n < 10:
		l[n] = 0
	if n == 1:
		print(1, 0)
	else:
		ar = {}
		dans = {0: 1000, 1: 1000, 2: 1000, 3: 1000, 4: 1000, 5: 1000, 6: 1000, 7: 1000, 8: 1000, 9: 1000, 10: 1000}
		l3(n, d, 0)
		for k in dans.keys():
			if dans[k] != 1000:
				print(k, dans[k])
				break


def digit_sum(n):
	return sum(map(int, str(n)))

def r_digit_sum(n):
	op = 0
	while n > 9:
		n = sum(map(int, str(n)))
		op += 1
	return (n, op)
T = int(input())
for t in range(T):
	(n, d) = map(int, input().split())
	oc = 0
	arr = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
	queue = [(n, 0)]
	while len(queue):
		(n, op) = queue.pop(0)
		(nd, nop) = r_digit_sum(n)
		if arr[nd] != -1:
			if arr[nd] < nop + op:
				continue
		if n < 10:
			if arr[n] != -1:
				if arr[n] > op:
					arr[n] = op
				else:
					continue
			else:
				arr[n] = op
		n_copy = n
		dc = 1
		while n_copy > 9:
			n_copy = digit_sum(n_copy)
			queue.append((n_copy, dc + op))
			dc += 1
		queue.append((n + d, op + 1))
	for i in range(1, 10):
		if arr[i] != -1:
			print(i, arr[i])
			break


import math

def getSum(a):
	sum = 0
	while a != 0:
		sum = sum + a % 10
		a = a // 10
	return sum
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	l = []
	l2 = []
	l.append(n)
	for i in range(3000):
		l.insert(2 * i + 1, getSum(l[i]))
		l.insert(2 * i + 2, l[i] + d)
	b = min(l)
	c = l.index(b)
	c = c + 1
	if n == 0 or d == 0:
		e = 0
	else:
		e = math.log(c, 2)
	print('%d %d' % (b, e))


def sum1(n):
	total = 0
	while n > 0:
		digit = n % 10
		total = total + digit
		n = n // 10
	return total
a = int(input())
for i in range(a):
	b = [int(i) for i in input().split()]
	c = []
	d = []
	g = []
	g = [0] * 11
	for i in range(11):
		c.append(b[0] + i * b[1])
	for i in range(11):
		d.append(i)
	for i in range(len(c)):
		l = 0
		k = c[i]
		r = 0
		while k // 10 != 0:
			k = sum1(k)
			l = l + 1
		d[i] = d[i] + l
		g[i] = k
	t = g.index(min(g))
	outf2 = min(g)
	c = []
	d = []
	for i in range(50):
		c.append(b[0] + i * b[1])
	for i in range(50):
		d.append(i)
	for i in range(len(c)):
		l = 0
		k = c[i]
		r = 0
		while k != outf2:
			k = sum1(k)
			l = l + 1
			if k // 10 == 0 and k != outf2:
				r = 1
				break
		if r == 0:
			d[i] = d[i] + l
		else:
			d[i] = 1000
	outl = []
	for i in range(len(c)):
		t = i
		r1 = []
		f = []
		for c1 in range(50):
			r1.append(t + c1 + 1)
		ct = sum1(c[i])
		for i1 in range(50):
			f.append(ct + i1 * b[1])
		for i2 in range(len(f)):
			l = 0
			k = f[i2]
			r = 0
			while k != outf2:
				k = sum1(k)
				l = l + 1
				if k // 10 == 0 and k != outf2:
					r = 1
					break
			if r == 0:
				r1[i2] = r1[i2] + l
			else:
				r1[i2] = 1000
		outl.append(min(r1))
	print(outf2, end=' ')
	print(min(min(outl), min(d)), end=' ')
	print()


def dSum(num):
	while num > 9:
		nstr = str(num)
		num = [int(x) for x in list(nstr)]
		num = sum(num)
	return num

def dS2(num):
	tot = 0
	while num > 0:
		tot += num % 10
		num //= 10
	return tot
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	temp = 10
	for i in range(10):
		num = n + d * i
		ds = dSum(num)
		if ds < temp:
			temp = ds
	q = [[n, 0]]
	dic = {}
	while len(q) > 0:
		el = q.pop(0)
		if el[0] < 10:
			if dic.get(el[0]) != None:
				continue
			dic[el[0]] = el[1]
		else:
			q.append([dS2(el[0]), el[1] + 1])
		q.append([el[0] + d, el[1] + 1])
		if el[0] == temp:
			break
	print(temp, dic[temp])


def digit_sum(n):
	s = 0
	while n > 0:
		s += n % 10
		n = n // 10
	return s
t = int(input())
for tt in range(t):
	(n, d) = map(int, input().split())
	dict = {}
	queue = []
	seq = 0
	queue.append((n, seq))
	dict[n] = 0
	while len(queue) > 0 and seq < 1000:
		(n, seq) = queue.pop(0)
		seq += 1
		x = digit_sum(n)
		if not x in dict:
			dict[x] = seq
			queue.append((x, seq))
		queue.append((n + d, seq))
	ans = min(dict)
	print(ans, dict[ans])


def digsum(n):
	s = 0
	while n > 0:
		s += n % 10
		n = n // 10
	return s
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	l = [[n, 0]]
	for i in range(10000):
		k = l.pop(0)
		l.append([k[0] + d, k[1] + 1])
		if k[0] >= 10:
			l.append([digsum(k[0]), k[1] + 1])
		else:
			l.append([k[0], k[1]])
	u = min(l)
	print(u[0], u[1])


def calc_digit_sum(N):
	if N <= 9:
		return N
	else:
		return sum(list((int(digit) for digit in str(N))))

def digit_sum(N):
	if N <= 9:
		return N
	else:
		return digit_sum(calc_digit_sum(N))

def compute_num_of_steps(N):
	if N <= 9:
		return 0
	else:
		return 1 + compute_num_of_steps(calc_digit_sum(N))

def minimize_digitsum(N, D, curr_num_of_steps, upper_bound, min_N, global_min_num_of_steps):
	if curr_num_of_steps >= upper_bound:
		return
	elif N <= 9:
		if N == min_N:
			global_min_num_of_steps[0] = curr_num_of_steps
		else:
			minimize_digitsum(N + D, D, curr_num_of_steps + 1, upper_bound, min_N, global_min_num_of_steps)
	else:
		minimize_digitsum(N + D, D, curr_num_of_steps + 1, upper_bound, min_N, global_min_num_of_steps)
		minimize_digitsum(calc_digit_sum(N), D, curr_num_of_steps + 1, upper_bound, min_N, global_min_num_of_steps)
T = int(input())
while T:
	(N, D) = list(map(int, input().split()))
	rec_digit_sum_N = digit_sum(N)
	rec_digit_sum_D = digit_sum(D)
	prev = rec_digit_sum_N
	min_N = rec_digit_sum_N
	min_num_of_increment_operations = 0
	for i in range(1, 9):
		curr = digit_sum(prev + rec_digit_sum_D)
		if curr < min_N:
			min_N = curr
			min_num_of_increment_operations = i
		prev = curr
	min_num_of_steps = min_num_of_increment_operations + compute_num_of_steps(N + min_num_of_increment_operations * D)
	curr_num_of_steps = 0
	upper_bound = min_num_of_steps
	global_min_num_of_steps = [min_num_of_steps]
	minimize_digitsum(N, D, curr_num_of_steps, upper_bound, min_N, global_min_num_of_steps)
	print(str(min_N) + ' ' + str(global_min_num_of_steps[0]))
	T -= 1


t = int(input())
for z in range(t):
	(n, d) = map(int, input().split(' '))
	a = []
	a.append((n, 0))
	i = 0
	while i < 2048:
		y = []
		for j in str(a[i][0]):
			y.append(j)
		y = [int(k) for k in y]
		s = sum(y)
		a.append((s, a[i][1] + 1))
		a.append((a[i][0] + d, a[i][1] + 1))
		i = i + 1
	q = min(a)
	print(q[0], q[1])


import math

def su(x):
	x = str(x)
	x = list(x)
	x = list(map(int, x))
	m = sum(x)
	return m
t = int(input())
for _ in range(t):
	l = [int(x) for x in input().split()]
	a = []
	a.append(l[0])
	for i in range(100000):
		a.append(su(a[i]))
		a.append(l[1] + a[i])
	d = min(a)
	f = a.index(d)
	qw = math.floor(math.log2(f + 1))
	print(d, qw)


def digisum(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 abc in range(T):
	(N, D) = input().split()
	(N, D) = (int(N), int(D))
	s = set()
	tempV = N
	for i in range(500000):
		if tempV <= 9:
			if not tempV in s:
				s.add(tempV)
				tempV = tempV + D
			else:
				break
		else:
			tempV = digisum(tempV)
	s = sorted(s)
	mn = 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 mn:
			ans = step - 1
			break
		q.append((num + D, step + 1))
		q.append((digisum(num), step + 1))
	print(str(mn) + ' ' + str(ans))


from queue import Queue

def digit(x):
	sum1 = 0
	for i in str(x):
		sum1 += int(i)
	return sum1
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	q = Queue()
	d1 = {}

	def digitsum(x, dict1={}):
		q.put(x)
		q.put(0)
		val = 0
		while not q.empty():
			t = q.get()
			if t == 0 and q.empty():
				break
			elif t == 0:
				q.put(0)
				val += 1
			else:
				t1 = digit(t)
				t2 = t + d
				if t1 not in dict1 and t2 not in dict1:
					q.put(t1)
					q.put(t2)
				if t not in dict1:
					dict1[t] = val
		dict1 = dict(sorted(dict1.items()))
		for i in dict1.keys():
			p = i
			break
		for j in dict1.values():
			y = j
			break
		return str(i) + ' ' + str(y)
	print(digitsum(n, d1))