Inflation has occurred in Berlandia, so the store needs to change the price of goods.

The current price of good $n$ is given. It is allowed to increase the price of the good by $k$ times, with $1 \le k \le m$, k is an integer. Output the roundest possible new price of the good. That is, the one that has the maximum number of zeros at the end.

For example, the number 481000 is more round than the number 1000010 (three zeros at the end of 481000 and only one at the end of 1000010).

If there are several possible variants, output the one in which the new price is maximal.

If it is impossible to get a rounder price, output $n \cdot m$ (that is, the maximum possible price).


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) —the number of test cases in the test.

Each test case consists of one line.

This line contains two integers: $n$ and $m$ ($1 \le n, m \le 10^9$). Where $n$ is the old price of the good, and the number $m$ means that you can increase the price $n$ no more than $m$ times.


-----Output-----

For each test case, output on a separate line the roundest integer of the form $n \cdot k$ ($1 \le k \le m$, $k$ — an integer).

If there are several possible variants, output the one in which the new price (value $n \cdot k$) is maximal.

If it is impossible to get a more rounded price, output $n \cdot m$ (that is, the maximum possible price).


-----Examples-----

Input
10
6 11
5 43
13 5
4 16
10050 12345
2 6
4 30
25 10
2 81
1 7
Output
60
200
65
60
120600000
10
100
200
100
7


-----Note-----

In the first case $n = 6$, $m = 11$. We cannot get a number with two zeros or more at the end, because we need to increase the price $50$ times, but $50 > m = 11$. The maximum price multiple of $10$ would be $6 \cdot 10 = 60$.

In the second case $n = 5$, $m = 43$. The maximum price multiple of $100$ would be $5 \cdot 40 = 200$.

In the third case, $n = 13$, $m = 5$. All possible new prices will not end in $0$, then you should output $n \cdot m = 65$.

In the fourth case, you should increase the price $15$ times.

In the fifth case, increase the price $12000$ times.

Difficulty: MEDIUM
Tags: Number theory

Complete search
Skill types: Complete search

Starter code:

Solutions:
import collections
import heapq
import sys
import math
import bisect
import os
from io import BytesIO, IOBase
input = sys.stdin.readline

def solve():
	(n, m) = list(map(int, input().split()))
	nn = n
	while n % 10 == 0:
		n //= 10
	tot = 1
	while n % 5 == 0 and tot * 2 <= m:
		tot *= 2
		n //= 5
	while n % 2 == 0 and tot * 5 <= m:
		tot *= 5
		n //= 2
	while tot * 10 <= m:
		tot *= 10
	print(nn * tot * (m // tot))
for i in range(int(input())):
	solve()


t = int(input(''))
C = [0] * t
for i in range(t):
	LRX = input('').split(' ')
	n = int(LRX[0])
	m = int(LRX[1])
	n2 = 1
	k = 1
	while n % 10 == 0:
		n //= 10
		n2 *= 10
	while n % 2 == 0:
		if 5 * k <= m:
			k = 5 * k
		n //= 2
		n2 *= 2
	while n % 5 == 0:
		if 2 * k <= m:
			k = 2 * k
		n //= 5
		n2 *= 5
	while 10 * k <= m:
		k *= 10
	k *= m // k
	C[i] = k * n * n2
for j in C:
	print(j)


import sys
input = sys.stdin.readline
t = int(input())

def maxi(n, m):
	(two, five) = divide(n)
	if two == five:
		if m < 10:
			return n * m
		else:
			return n * 10 ** (len(str(m)) - 1) * int(str(m)[0])
	elif two > five:
		two -= five
		get_more = get_mores(5, m)
		if get_more > two:
			m = m // 5 ** two
			n *= 5 ** two
			return n * 10 ** (len(str(m)) - 1) * int(str(m)[0])
		return n * 5 ** get_more * (m // 5 ** get_more)
	else:
		five -= two
		get_more = get_mores(2, m)
		if get_more > five:
			m = m // 2 ** five
			n *= 2 ** five
			return n * 10 ** (len(str(m)) - 1) * int(str(m)[0])
		return n * 2 ** get_more * (m // 2 ** get_more)

def get_mores(what, m):
	tmp = what
	get_more = 0
	while True:
		if m // tmp > 0:
			get_more += 1
			tmp *= what
			continue
		break
	return get_more

def divide(n):
	five = 0
	tmp = 5
	while True:
		if n % tmp == 0:
			five += 1
			tmp *= 5
			continue
		break
	two = 0
	tmp = 2
	while True:
		if n % tmp == 0:
			two += 1
			tmp *= 2
			continue
		break
	return (two, five)
for _ in range(t):
	(n, m) = map(int, input().split())
	print(maxi(n, m))


t = int(input())
answers = []
for _ in range(t):
	(n, m) = map(int, input().split())
	(n_, m_) = (n, m)
	(two, five) = (0, 0)
	while n_ % 2 == 0:
		n_ //= 2
		two += 1
	while n_ % 5 == 0:
		n_ //= 5
		five += 1
	tmp = 1
	if two > five:
		for i in range(two - five):
			if m_ < 5:
				break
			m_ //= 5
			tmp *= 5
	else:
		for i in range(five - two):
			if m_ < 2:
				break
			m_ //= 2
			tmp *= 2
	k = int(str(m_)[0]) * 10 ** (len(str(m_)) - 1) * tmp
	answers.append(n * k)
for answer in answers:
	print(answer)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	fiveCount = twoCount = 0
	hold = n
	while hold:
		if hold % 2 == 0:
			twoCount += 1
			hold //= 2
		elif hold % 5 == 0:
			fiveCount += 1
			hold //= 5
		else:
			break
	if fiveCount == twoCount:
		curr = 1
		tmp = 10
		while tmp > 1:
			if tmp * curr <= m:
				curr *= tmp
			else:
				tmp -= 1
		print(curr * n)
	elif fiveCount > twoCount:
		fiveCount -= twoCount
		curr = 1
		while fiveCount and curr * 2 <= m:
			curr *= 2
			fiveCount -= 1
		if fiveCount:
			temp = 10
			while temp > 1:
				if curr * temp <= m:
					curr *= temp
				else:
					temp -= 1
			print(curr * n)
		else:
			tmp = 10
			while tmp > 1:
				if tmp * curr <= m:
					curr *= tmp
				else:
					tmp -= 1
			print(curr * n)
	else:
		twoCount -= fiveCount
		curr = 1
		while twoCount and curr * 5 <= m:
			curr *= 5
			twoCount -= 1
		if twoCount:
			temp = 10
			while temp > 1:
				if curr * temp <= m:
					curr *= temp
				else:
					temp -= 1
			print(curr * n)
		else:
			tmp = 10
			while tmp > 1:
				if tmp * curr <= m:
					curr *= tmp
				else:
					tmp -= 1
			print(curr * n)


def solve():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		cnt2 = cnt5 = 0
		temp_n = n
		while n and n % 2 == 0:
			n //= 2
			cnt2 += 1
		while n and n % 5 == 0:
			n //= 5
			cnt5 += 1
		k = 1
		while cnt2 < cnt5 and k * 2 <= m:
			cnt2 += 1
			k *= 2
		while cnt5 < cnt2 and k * 5 <= m:
			cnt5 += 1
			k *= 5
		while 10 * k <= m:
			k *= 10
		if k == 1:
			print(temp_n * m)
		else:
			k *= int(m / k)
			print(temp_n * k)
solve()


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	c2 = c5 = 0
	nn = n
	while nn % 2 == 0:
		nn //= 2
		c2 += 1
	while nn % 5 == 0:
		nn //= 5
		c5 += 1
	mm = m
	zw = min(c2, c5)
	if c2 > c5:
		s5 = 0
		while mm > 5 and s5 + c5 < c2:
			s5 += 1
			mm //= 5
		while mm > 10:
			mm //= 10
			c2 += 1
			c5 += 1
		c5 += s5
	elif c2 < c5:
		s2 = 0
		while mm > 2 and s2 + c2 < c5:
			s2 += 1
			mm //= 2
		while mm > 10:
			mm //= 10
			c2 += 1
			c5 += 1
		c2 += s2
	else:
		while mm > 10:
			mm //= 10
			c2 += 1
			c5 += 1
	if zw >= min(c2, c5):
		print(n * m)
	else:
		print(nn * 2 ** c2 * 5 ** c5 * mm)


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	ans = n
	k = 1
	while n > 0 and n % 10 == 0:
		n //= 10
	while n > 0 and n % 5 == 0:
		n //= 5
		if k * 2 <= m:
			k *= 2
		else:
			break
	while n > 0 and n % 2 == 0:
		n //= 2
		if k * 5 <= m:
			k *= 5
		else:
			break
	while k * 10 <= m:
		k *= 10
	k = m // k * k
	print(ans * k)


K = lambda : [*map(int, input().split())]
for _ in ' ' * K()[0]:
	(n, m) = K()
	N = n
	while n % 10 == 0:
		n //= 10
	c = 1
	while n % 2 == 0 and c * 5 <= m:
		c *= 5
		n //= 2
	while n % 5 == 0 and c * 2 <= m:
		c *= 2
		n //= 5
	while c * 10 <= m:
		c *= 10
	print(N * c * (m // c))


I = lambda : int(input())
Is = lambda : map(int, input().split())
Li = lambda : list(map(int, input().split()))

def solve():
	(a, b) = Is()
	res = 0
	ans = 0
	tt = a
	while a % 10 == 0:
		a //= 10
	while not a & 1 and b >= 5:
		tt *= 5
		a //= 2
		b //= 5
	while a % 5 == 0 and b >= 2:
		tt *= 2
		a //= 5
		b //= 2
	while b >= 10:
		tt *= 10
		b //= 10
	tt *= b
	print(tt)
	return 1
t = I()
while t:
	solve()
	t -= 1


t = int(input())
while t > 0:
	t = t - 1
	(n, m) = map(int, input().split())
	z = n
	c = 0
	while n != 0 and n % 10 == 0:
		n = n // 10
	limit = 1
	while n != 0 and n % 5 == 0 and (limit * 2 <= m):
		n = n // 5
		limit = limit * 2
	while n != 0 and n % 2 == 0 and (limit * 5 <= m):
		n = n // 2
		limit = limit * 5
	while limit * 10 <= m:
		limit = limit * 10
	limit = limit * int(m / limit)
	print(limit * z)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(n2, n5) = (0, 0)
	nn = n
	while not nn % 2:
		n2 += 1
		nn //= 2
	while not nn % 5:
		n5 += 1
		nn //= 5
	k = 1
	if n2 > n5:
		while k * 5 <= m and n2 > n5:
			k *= 5
			n5 += 1
	elif n2 < n5:
		while k * 2 <= m and n2 < n5:
			k *= 2
			n2 += 1
	while k * 10 <= m:
		k *= 10
	k *= m // k
	print(n * k)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	ans = n
	k = 1
	while n % 10 == 0:
		n = n / 10
	while n % 5 == 0:
		n = n / 5
		if k * 2 <= m:
			k *= 2
		else:
			break
	while n % 2 == 0:
		n = n / 2
		if k * 5 <= m:
			k *= 5
		else:
			break
	while k * 10 <= m:
		k *= 10
	k = m // k * k
	print(ans * k)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	temp = n
	cnt2 = 0
	while temp % 2 == 0:
		cnt2 += 1
		temp = temp // 2
	cnt5 = 0
	while temp % 5 == 0:
		cnt5 += 1
		temp = temp // 5
	value = 1
	if cnt5 > cnt2:
		p = cnt5 - cnt2
		while p > 0:
			if value * 2 <= m:
				value = value * 2
			else:
				break
			p = p - 1
	elif cnt2 > cnt5:
		p = cnt2 - cnt5
		while p > 0:
			if value * 5 <= m:
				value = value * 5
			else:
				break
			p = p - 1
	while True:
		if value * 10 <= m:
			value = value * 10
		else:
			break
	u = m // value
	res = u * value
	ans = n * res
	print(ans)
	t = t - 1


N = int(input())

def cal_2_5(x):
	(count_2, count_5) = (0, 0)
	while x % 2 == 0:
		count_2 += 1
		x /= 2
	while x % 5 == 0:
		count_5 += 1
		x /= 5
	return (count_2, count_5)

def solve():
	(n, m) = [int(g) for g in input().split()]
	(count_2, count_5) = cal_2_5(n)
	count = 1
	while count_2 < count_5:
		if count * 2 <= m:
			count_2 += 1
			count *= 2
		else:
			break
	while count_5 < count_2:
		if count * 5 <= m:
			count_5 += 1
			count *= 5
		else:
			break
	while count < m:
		if count * 10 <= m:
			count *= 10
		else:
			break
	if count == 1:
		return n * m
	else:
		count = m // count * count
		return n * count
for _ in range(N):
	print(solve())


def degree(a, c):
	ans = 0
	while a % c == 0:
		a //= c
		ans += 1
	return ans
for _ in range(int(input())):
	(a, n) = map(int, input().split())
	da2 = degree(a, 2)
	da5 = degree(a, 5)
	kaka = 1
	while kaka < n and da5 != da2:
		if da5 > da2:
			if kaka * 2 > n:
				break
			kaka *= 2
			da2 += 1
		elif da2 > da5:
			if kaka * 5 > n:
				break
			kaka *= 5
			da5 += 1
	s = str(n // kaka)
	print(int(s[0]) * a * 10 ** (len(s) - 1) * kaka)


number_of_tests = int(input())
for _ in range(number_of_tests):
	(n, m) = map(int, input().split())
	n_backup = n
	m_backup = m
	tens = 0
	twos = 0
	fives = 0
	while n % 10 == 0:
		n = n / 10
		tens += 1
	while n % 2 == 0 and 5 ** (twos + 1) <= m:
		n = n / 2
		twos += 1
	while n % 5 == 0 and 2 ** (fives + 1) <= m:
		n = n / 5
		fives += 1
	if fives > 0:
		new_m = 2 ** fives * int(str(m // 2 ** fives)[0]) * 10 ** (len(str(m // 2 ** fives)) - 1)
	elif twos > 0:
		new_m = 5 ** twos * int(str(m // 5 ** twos)[0]) * 10 ** (len(str(m // 5 ** twos)) - 1)
	elif len(str(m)) > 1:
		new_m = int(str(m)[0]) * 10 ** (len(str(m)) - 1)
	else:
		new_m = m
	print(n_backup * new_m)


def run_task():
	(n, m) = [int(x) for x in input().split()]
	if m == 1:
		return n
	r = n
	a = 0
	while r % 2 == 0:
		a += 1
		r //= 2
	b = 0
	while r % 5 == 0:
		b += 1
		r //= 5
	num = 2 if a < b else 5
	k = 1
	for i in range(abs(b - a)):
		if k * num > m:
			return k * (m // k) * n
		k *= num
	while True:
		if k * 10 > m:
			return k * (m // k) * n
		k *= 10
t = int(input())
for _ in range(t):
	print(run_task())


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(cnt2, cnt5) = (0, 0)
	tempn = n
	k = 1
	while tempn % 2 == 0:
		cnt2 += 1
		tempn //= 2
	while tempn % 5 == 0:
		cnt5 += 1
		tempn //= 5
	while cnt2 < cnt5 and 2 * k <= m:
		k *= 2
		cnt2 += 1
	while cnt2 > cnt5 and 5 * k <= m:
		k *= 5
		cnt5 += 1
	while 10 * k <= m:
		k *= 10
	k = k * (m // k)
	print(n * k)


inp = []
for _ in range(int(input())):
	inp.append([int(x) for x in input().split(' ')])

def f2(x):
	c = 0
	while x % 2 == 0:
		c += 1
		x = x // 2
	return c

def f5(x):
	c = 0
	while x % 5 == 0:
		c += 1
		x = x // 5
	return c
for (n, m) in inp:
	(t, f) = (f2(n), f5(n))
	(t1, f1) = (0, 0)
	p = 1
	while p < m:
		if t + t1 == f + f1:
			if p * 10 <= m:
				p *= 10
				t1 += 1
				f1 += 1
			else:
				break
		elif t + t1 < f + f1:
			if p * 2 <= m:
				p *= 2
				t1 += 1
			else:
				break
		elif p * 5 <= m:
			p *= 5
			f1 += 1
		else:
			break
	if t1 + t > 0 and f1 + f > 0:
		k = m // p
		print(n * k * p)
	else:
		print(n * m)


import os
import math
import collections
import bisect
import functools
import itertools
import heapq
from collections import deque

def primeFactor(num):
	i = 2
	ans = set()
	(c2, c5) = (0, 0)
	while num % 2 == 0:
		c2 += 1
		num //= 2
	while num % 5 == 0:
		c5 += 1
		num //= 5
	return (c2, c5)

def solve(n, m):
	(c2, c5) = primeFactor(n)
	k = 1
	while c2 < c5 and k * 2 <= m:
		k *= 2
		c2 += 1
	while c2 > c5 and k * 5 <= m:
		k *= 5
		c5 += 1
	while k * 10 <= m:
		k *= 10
		c2 += 1
		c5 += 1
	if k == 1:
		return n * m
	k = k * (m // k)
	return n * k
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(solve(n, m))


def zero(req, c, num):
	temp = req
	res = 0
	while temp < num and res < c:
		temp = temp * req
		res += 1
	return res

def solve(n, k):
	temp = n
	p = k
	zerop = 0
	while temp % 10 == 0:
		temp = temp // 10
	c2 = c5 = 0
	while temp % 2 == 0:
		temp = temp // 2
		c2 += 1
	while temp % 5 == 0:
		temp = temp // 5
		c5 += 1
	if c2:
		req = 5
		res = zero(req, c2, k)
	else:
		req = 2
		res = zero(req, c5, k)
	p = p // req ** res
	while p // 10:
		p = p // 10
		zerop += 1
	answer = 10 ** zerop * req ** res
	answer = k // answer * answer * n
	if answer == 0:
		print(n * k)
		return
	print(answer)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	solve(n, k)


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	k = 1
	val = n
	while n % 10 == 0:
		n = n // 10
	while n % 5 == 0:
		n = n // 5
		if k * 2 <= m:
			k = k * 2
		else:
			break
	while n % 2 == 0:
		n = n // 2
		if k * 5 <= m:
			k = k * 5
		else:
			break
	while k * 10 <= m:
		k = k * 10
	k = m // k * k
	print(val * k)


def digit(n):
	ans = 0
	while n > 0:
		ans += 1
		n = n // 10
	return ans

def twos(n):
	ans = 0
	while n % 2 == 0 and n > 0:
		ans += 1
		n = n // 2
	return ans

def fives(n):
	ans = 0
	while n % 5 == 0 and n > 0:
		ans += 1
		n = n // 5
	return ans

def tens(n):
	ans = 0
	while n % 10 == 0 and n > 0:
		ans += 1
		n = n // 10
	return ans
for _ in range(int(input())):
	(m, k) = map(int, input().split())
	c = tens(m)
	m = m // 10 ** c
	a = twos(m)
	b = fives(m)
	x = 2 ** b * 5 ** a
	ans = 0
	if k == x:
		ans = m * 10 ** c * x
	elif k > x:
		y = k // x
		di = digit(y)
		y = y // 10 ** (di - 1)
		ans = y * 10 ** (di - 1) * x * m * 10 ** c
	elif a == 0:
		while x > k:
			x = x // 2
		ans = m * 10 ** c * x
	else:
		while x > k:
			x = x // 5
		e = k // x
		ans = m * 10 ** c * x * e
	print(ans)


from math import log
for i in range(int(input())):
	(n, m) = map(int, input().split())
	(two_count, five_count, p) = (0, 0, n)
	while p % 2 == 0:
		p //= 2
		two_count += 1
	while p % 5 == 0:
		p //= 5
		five_count += 1
	ans = 1
	k = min(two_count, five_count)
	two_count -= k
	five_count -= k
	if two_count > 0:
		ans = 5 ** min(int(log(m, 5)), two_count)
	if five_count > 0:
		ans = 2 ** min(int(log(m, 2)), five_count)
	ans *= 10 ** int(log(m / ans, 10))
	print(ans * n * max(m // ans, 1))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	x = n
	div5 = 0
	div2 = 0
	while x % 5 == 0 and n > 0:
		x //= 5
		div5 += 1
	while x % 2 == 0 and n > 0:
		x //= 2
		div2 += 1
	k = 1
	if div5 > div2:
		while m >= k * 2 and div5 > div2:
			k *= 2
			div5 -= 1
	elif div2 > div5:
		while m >= k * 5 and div2 > div5:
			k *= 5
			div2 -= 1
	if k == 1 and m < 10:
		print(n * m)
	else:
		while m >= k * 10:
			k *= 10
		a = k
		while m >= k + a:
			k += a
		print(n * k)


n = int(input())
for _ in range(n):
	(n, m) = map(int, input().split())
	x = n
	while x % 10 == 0:
		x = x / 10
	n5 = 0
	while x % 5 == 0:
		x = x / 5
		n5 += 1
	n2 = 0
	while x % 2 == 0:
		x = x / 2
		n2 += 1
	k = 1
	p = 0
	while k * 2 <= m and p < n5:
		k *= 2
		p += 1
	p = 0
	while k * 5 <= m and p < n2:
		k *= 5
		p += 1
	while k * 10 <= m:
		k *= 10
	if k == 1:
		print(n * m)
	else:
		for i in range(9, 1, -1):
			if k * i <= m:
				k *= i
		print(n * k)


def f(n, m):
	val_2 = 0
	val_5 = 0
	k = n
	while k % 2 == 0:
		val_2 += 1
		k //= 2
	while k % 5 == 0:
		val_5 += 1
		k //= 5
	total = 1
	check_2 = False
	while val_2 < val_5 and total <= m:
		total *= 2
		val_2 += 1
		check_2 = True
	if check_2 and total > m:
		total //= 2
		val_2 -= 1
	check_5 = False
	while val_5 < val_2 and total <= m:
		total *= 5
		val_5 += 1
		check_5 = True
	if check_5 and total > m:
		total //= 5
		val_5 -= 1
	check_25 = False
	while val_2 == val_5 and total <= m:
		total *= 10
		val_2 += 1
		val_5 += 1
		check_25 = True
	if check_25 and total > m:
		total //= 10
		val_2 -= 1
		val_5 -= 1
	if m % total == 0:
		total *= m // total
	else:
		total *= int(m / total)
	return n * total
t = int(input())
for i in range(t):
	(n, m) = [int(el) for el in input().split(' ')]
	print(f(n, m))


def factor(g, h):
	c = 0
	while h % g == 0:
		c += 1
		h //= g
	return c
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = factor(2, n)
	b = factor(5, n)
	if a == b:
		if m >= 10:
			k = 1
			while k * 10 <= m:
				k *= 10
			i = 1
			while k * i <= m:
				i += 1
			k *= i - 1
			print(n * k)
		else:
			print(n * m)
	elif a > b:
		ct = a - b
		if m >= 5:
			k = 1
			while k * 5 <= m and ct > 0:
				k *= 5
				ct -= 1
			while k * 10 <= m:
				k *= 10
			i = 1
			while k * i <= m:
				i += 1
			k *= i - 1
			print(n * k)
		else:
			print(n * m)
	elif a < b:
		ct = b - a
		if m >= 2:
			k = 1
			while k * 2 <= m and ct > 0:
				k *= 2
				ct -= 1
			while k * 10 <= m:
				k *= 10
			i = 1
			while k * i <= m:
				i += 1
			k *= i - 1
			print(n * k)
		else:
			print(n * m)


def find_2(x):
	res = 0
	while x % 2 == 0:
		res += 1
		x = x / 2
	return res

def find_5(x):
	res = 0
	while x % 5 == 0:
		res += 1
		x = x / 5
	return res

def balance_5(max_, x, n, m):
	while x * 2 <= max_ and n != m:
		x *= 2
		n += 1
	return x

def balance_2(max_, x, n, m):
	while x * 5 <= max_ and n != m:
		x *= 5
		m += 1
	return x

def cal_0(x):
	res = 0
	while x % 10 == 0:
		res += 1
		x /= 10
	return res
n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	n = find_2(x)
	m = find_5(x)
	max_ = x * y
	if n < m:
		res = balance_5(max_, x, n, m)
	elif n > m:
		res = balance_2(max_, x, n, m)
	else:
		res = x
	while max_ // res >= 10:
		res *= 10
	res = max_ // res * res
	if res % 10 == 0:
		print(res)
	else:
		print(max_)


def get_factor_count(num, f):
	c = 0
	while num % f == 0:
		num //= f
		c += 1
	return c

def roundest_int(cprice, m):
	c2f = get_factor_count(cprice, 2)
	c5f = get_factor_count(cprice, 5)
	k = 1
	if c2f > c5f:
		diff = c2f - c5f
		while diff > 0 and k * 5 <= m:
			k *= 5
			diff -= 1
	elif c5f > c2f:
		diff = c5f - c2f
		while diff > 0 and k * 2 <= m:
			k *= 2
			diff -= 1
	while True:
		if 10 * k < m:
			k *= 10
		else:
			last = m // k
			if last > 0:
				k *= last
			break
	return k * n
t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split()]
	print(roundest_int(n, m))


def solve(n, m):
	count_2 = 0
	count_5 = 0
	t = n
	while t % 2 == 0:
		count_2 += 1
		t = t // 2
	t = n
	while t % 5 == 0:
		count_5 += 1
		t = t // 5
	x = 1
	cp_n = n
	while count_5 > count_2 and x * 2 <= m:
		x = x * 2
		cp_n *= 2
		count_2 += 1
	while count_5 < count_2 and x * 5 <= m:
		x = x * 5
		cp_n *= 5
		count_5 += 1
	while x * 10 <= m:
		cp_n *= 10
		x = x * 10
	cp_n = cp_n * (m // x)
	return cp_n
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(solve(n, m))
pass


t = int(input())
for tt in range(t):
	(n, m) = [int(x) for x in input().split()]
	(n5, n2, m5, m2) = (0, 0, 0, 0)
	nt = n
	while nt % 5 == 0:
		n5 += 1
		nt //= 5
	while nt % 2 == 0:
		n2 += 1
		nt //= 2
	if n5 >= n2:
		mul = 1
		for i in range(1, n5 - n2 + 1):
			if mul * 2 > m:
				break
			mul *= 2
		while mul * 10 <= m:
			mul *= 10
		mul *= m // mul
		print(n * mul)
	else:
		mul = 1
		for i in range(1, n2 - n5 + 1):
			if mul * 5 > m:
				break
			mul *= 5
		while mul * 10 <= m:
			mul *= 10
		mul *= m // mul
		print(n * mul)


TT = int(input())
while TT:
	(n, m) = list(map(int, input().split()))
	t = 1
	left = m
	s = str(n)
	s = s.strip('0')
	now = 0
	while (s[-1] == '2' or s[-1] == '4' or s[-1] == '8' or (s[-1] == '5') or (s[-1] == '6')) and left >= 2:
		if s[-1] == '5':
			s = str(int(s) * 2)
			k = left
			left /= 2
			t *= 2
			s = s.strip('0')
			now = 2
		else:
			if left < 5:
				break
			s = str(int(s) * 5)
			k = left
			left /= 5
			t *= 5
			s = s.strip('0')
			now = 5
	while left >= 10:
		t *= 10
		left /= 10
	small = m // t
	print(n * t * small)
	TT -= 1


t = int(input())

def get_count_of_p(n, p):
	count = 0
	while n % p == 0:
		count += 1
		n /= p
	return count
for t0 in range(t):
	(n, m) = list(map(int, input().split()))
	count_of_2 = get_count_of_p(n, 2)
	count_of_5 = get_count_of_p(n, 5)
	mul = 1
	while True:
		if count_of_2 == count_of_5:
			if 10 * mul <= m:
				mul *= 10
			else:
				break
		elif count_of_2 > count_of_5:
			if 5 * mul <= m:
				mul *= 5
				count_of_5 += 1
			else:
				break
		elif 2 * mul <= m:
			mul *= 2
			count_of_2 += 1
		else:
			break
	mul *= int(m / mul)
	print(n * mul)


T = int(input())

def c(n, x):
	ans = 0
	while n % x == 0:
		ans += 1
		n //= x
	return ans
for Ti in range(T):
	t = input().split()
	(n, m) = (int(t[0]), int(t[1]))
	x = 1
	(c2, c5) = (c(n, 2), c(n, 5))
	if c2 > c5:
		i = c2 - c5
		while i > 0:
			y = x * 5
			if y <= m:
				x = y
				i -= 1
			else:
				break
	elif c2 < c5:
		i = c5 - c2
		while i > 0:
			y = x << 1
			if y <= m:
				x = y
				i -= 1
			else:
				break
	while 1:
		y = x * 10
		if y <= m:
			x = y
		else:
			break
	x = m // x * x
	print(x * n)


t = int(input())
for i in range(t):
	(a, b) = list(map(int, input().split(' ')))
	ina = a
	a2 = 0
	a5 = 0
	while a % 5 == 0:
		a5 += 1
		a //= 5
	while a % 2 == 0:
		a2 += 1
		a //= 2
	target = 1
	while a2 < a5 and target * 2 <= b or (a2 > a5 and target * 5 <= b) or target * 10 <= b:
		if a2 < a5:
			target *= 2
			a2 += 1
		elif a2 > a5:
			target *= 5
			a5 += 1
		else:
			a2 += 1
			a5 += 1
			target *= 10
	assert target <= b
	target = b // target * target
	print(ina * target)


t = input()
for tt in range(int(t)):
	(n, m) = map(int, input().split())
	c2 = 0
	u = n
	while u % 2 == 0:
		u //= 2
		c2 += 1
	c5 = 0
	u = n
	while u % 5 == 0:
		u //= 5
		c5 += 1
	while True:
		if c2 > c5:
			if m < 5:
				n *= m
				break
			n *= 5
			m //= 5
			c5 += 1
		elif c2 < c5:
			if m < 2:
				n *= m
				break
			n *= 2
			m //= 2
			c2 += 1
		else:
			if m < 10:
				n *= m
				break
			n *= 10
			m //= 10
	print(n)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	st = n
	two = 0
	five = 0
	k = 1
	while n % 2 == 0:
		n //= 2
		two += 1
	while n % 5 == 0:
		n //= 5
		five += 1
	while two < five and k * 2 <= m:
		two += 1
		k *= 2
	while five < two and k * 5 <= m:
		five += 1
		k *= 5
	while k * 10 <= m:
		k *= 10
	if k == 1:
		print(st * m)
	else:
		k *= m // k
		print(st * k)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	fives = 0
	n_copy = n
	while n_copy % 5 == 0:
		fives += 1
		n_copy //= 5
	twos = 0
	n_copy = n
	while n_copy % 2 == 0:
		twos += 1
		n_copy //= 2
	sol = 1
	diff = twos - fives
	while diff > 0 and sol * 5 <= m:
		sol *= 5
		diff -= 1
	while diff < 0 and sol * 2 <= m:
		sol *= 2
		diff += 1
	while sol * 10 <= m:
		sol *= 10
	t_sol = sol
	for i in range(1, 11):
		if t_sol * i <= m:
			sol = t_sol * i
	print(sol * n)


nb_test_case = int(input())
for i in range(0, nb_test_case):
	lists = input().split()
	n = int(lists[0])
	m = int(lists[1])
	stock = n
	two_exposant = 0
	five_exposant = 0
	while stock % 2 == 0:
		stock = stock // 2
		two_exposant += 1
	while stock % 5 == 0:
		stock = stock // 5
		five_exposant += 1
	multiplicateur = 1
	while two_exposant < five_exposant and multiplicateur * 2 <= m:
		multiplicateur *= 2
		two_exposant += 1
	while five_exposant < two_exposant and multiplicateur * 5 <= m:
		multiplicateur *= 5
		five_exposant += 1
	while multiplicateur * 10 <= m:
		multiplicateur *= 10
	for j in range(9, -1, -1):
		if multiplicateur * j <= m:
			multiplicateur *= j
			break
	print(n * multiplicateur)


def log(a: int, x: int, p=1):
	ans = 0
	res = p
	while res <= a:
		res *= x
		ans += 1
	return ans - 1

def g(x: int):
	ans = {2: 0, 5: 0}
	while x % 2 == 0:
		x //= 2
		ans[2] += 1
	while x % 5 == 0:
		x //= 5
		ans[5] += 1
	return ans

def f():
	(n, k) = map(int, input().split())
	x = g(n)
	ans = -1
	if x[2] > x[5]:
		x[2] -= x[5]
		y = log(k, 5)
		if y < x[2]:
			ans = max(5 ** y * (k // 5 ** y) * n, ans)
		else:
			z = log(k, 10, p=5 ** x[2])
			ans = max(5 ** x[2] * 10 ** z * n * (k // (5 ** x[2] * 10 ** z)), ans)
	else:
		x[5] -= x[2]
		y = log(k, 2)
		if y < x[5]:
			ans = max(ans, 2 ** y * (k // 2 ** y) * n)
		else:
			z = log(k, 10, p=2 ** x[5])
			ans = max(2 ** x[5] * 10 ** z * n * (k // (2 ** x[5] * 10 ** z)), ans)
	return ans
for i in range(int(input())):
	print(f())


from math import log

def calcPow(n, k):
	answer = 0
	while n % k == 0:
		answer += 1
		n /= k
	return answer
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	tens = calcPow(n, 10)
	twos = calcPow(n, 2) - tens
	fives = calcPow(n, 5) - tens
	maxTwos = int(log(m, 2))
	maxFives = int(log(m, 5))
	curr = 1
	if twos:
		curr = pow(5, min(twos, maxFives))
	elif fives:
		curr = pow(2, min(fives, maxTwos))
	while curr * 10 <= m:
		curr *= 10
	curr = curr * (m // curr)
	print(n * curr)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	e = m
	out = 1
	twos = 0
	fives = 0
	l = []
	ee = n
	while ee % 2 == 0:
		twos += 1
		ee = ee // 2
	while ee % 5 == 0:
		fives += 1
		ee = ee // 5
	cond = False
	while twos > fives and m // 5 > 0:
		n *= 5
		m = m // 5
		fives += 1
		cond = True
	while fives > twos and m // 2 > 0:
		n *= 2
		m = m // 2
		twos += 1
		cond = True
	while m // 10 > 0:
		n *= 10
		m = m // 10
		cond = True
	if cond:
		print(n * m)
	else:
		print(n * m)


import math
t = int(input())
for x in range(t):
	(n, m) = map(int, input().split(' '))
	a = n
	n_ = [0, 0]
	while a % 2 == 0 or a % 5 == 0:
		if a % 2 == 0:
			a = a // 2
			n_[0] += 1
		if a % 5 == 0:
			a = a // 5
			n_[1] += 1
	k = 1
	while n_[0] < n_[1] and k * 2 <= m:
		n_[0] += 1
		k *= 2
	while n_[0] > n_[1] and k * 5 <= m:
		n_[1] += 1
		k *= 5
	while k * 10 <= m:
		k *= 10
	if k == 1:
		k = m
	else:
		k *= m // k
	print(n * k)


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	n0 = n
	cnt2 = 0
	cnt5 = 0
	k = 1
	while n > 0 and n % 2 == 0:
		n //= 2
		cnt2 += 1
	while n > 0 and n % 5 == 0:
		n //= 5
		cnt5 += 1
	while cnt2 < cnt5 and k * 2 <= m:
		cnt2 += 1
		k *= 2
	while cnt5 < cnt2 and k * 5 <= m:
		cnt5 += 1
		k *= 5
	while k * 10 <= m:
		k *= 10
	if k == 1:
		print(n0 * m)
	else:
		k *= m // k
		print(n0 * k)


def count(n, factor):
	ct = 0
	while n % factor == 0:
		n = n // factor
		ct += 1
	return ct
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	k = 1
	two = count(n, 2)
	five = count(n, 5)
	zero = min(two, five)
	while k <= m:
		if zero < five:
			if 2 * k < m:
				k *= 2
				zero += 1
			else:
				break
		elif zero < two:
			if 5 * k < m:
				k *= 5
				zero += 1
			else:
				break
		elif 10 * k < m:
			k *= 10
			zero += 1
		else:
			break
	print(n * (m // k) * k)


t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	x = 0
	n2 = n
	while n2 % 2 == 0:
		n2 //= 2
		x += 1
	y = 0
	n5 = n
	while n5 % 5 == 0:
		n5 //= 5
		y += 1
	k = 1
	if x > y:
		count = 0
		while k * 5 <= m and count < x - y:
			k *= 5
			count += 1
	else:
		count = 0
		while k * 2 <= m and count < y - x:
			k *= 2
			count += 1
	while k * 10 <= m:
		k *= 10
	for j in range(9, 0, -1):
		if k * j <= m:
			k *= j
			break
	print(n * k)


from math import log
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	N = n
	twos = fives = 0
	while not n % 2 or not n % 5:
		if not n % 2:
			n //= 2
			twos += 1
		if not n % 5:
			n //= 5
			fives += 1
	if twos > fives:
		twos -= fives
		fives = 0
	else:
		fives -= twos
		twos = 0
	currTwos = min(int(log(k, 2)), fives)
	curr = 2 ** currTwos
	currFives = 0
	while curr * 5 < k and currFives < twos:
		curr *= 5
		currFives += 1
	while curr * 10 < k:
		curr *= 10
	print(N * curr * (k // curr))


def end_zeros(num):
	n = 0
	while num % 10 == 0:
		n += 1
		num = num / 10
	return n

def solve(n, m):
	max_const = 1
	temp = n
	while n % 10 == 0:
		n //= 10
	while n % 2 == 0 and max_const * 5 <= m:
		max_const *= 5
		n //= 2
	while n % 5 == 0 and max_const * 2 <= m:
		max_const *= 2
		n //= 5
	while max_const * 10 <= m:
		max_const *= 10
	return temp * (m // max_const) * max_const
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	print(solve(n, m))


from sys import stdin, stdout
t = int(stdin.readline().strip())
for _ in range(t):
	(n, m) = map(int, stdin.readline().split())
	max_2 = 0
	max_5 = 0
	curr = 2
	while curr <= n:
		if n % curr == 0:
			max_2 += 1
		curr *= 2
	curr = 5
	while curr <= n:
		if n % curr == 0:
			max_5 += 1
		curr *= 5
	(max_2, max_5) = (max_2 - min(max_2, max_5), max_5 - min(max_2, max_5))
	multi = 1
	added = False
	while max_2 > 0 and multi * 5 <= m:
		max_2 -= 1
		multi *= 5
		added = True
	while max_5 > 0 and multi * 2 <= m:
		max_5 -= 1
		multi *= 2
		added = True
	while multi * 10 <= m:
		multi *= 10
		added = True
	multi *= m // multi
	if not added:
		print(n * m)
	else:
		print(n * multi)


for _ in range(0, int(input())):
	(a, b) = map(int, input().split())
	(c2, c5, s, t) = [0, 0, 0, 0]
	while a % 2 == 0:
		c2 += 1
		a //= 2
	while a % 5 == 0:
		c5 += 1
		a //= 5
	while True:
		if c2 > c5 and b >= 5:
			b //= 5
			c5 += 1
		elif c2 > c5:
			break
		if c2 < c5 and b >= 2:
			b //= 2
			c2 += 1
		elif c2 < c5:
			break
		if c2 == c5 and b >= 10:
			b //= 10
			c2 += 1
			c5 += 1
		elif c2 == c5:
			break
	print(a * b * 2 ** c2 * 5 ** c5)


import math
for t in range(int(input())):
	(n, m) = map(int, input().split())
	f = 0
	ans = -1
	for j in range(18, 0, -1):
		x = 10 ** j
		g = math.gcd(n, x)
		x = x // g
		if x <= m:
			ans = x
			break
	if ans == -1:
		print(n * m)
		continue
	k = m // ans
	print(ans * n * k)


import math
t = int(input())

def lcm(a, b):
	return a * b // math.gcd(a, b)
for i in range(1, t + 1):
	(n, m) = [int(v) for v in input().split()]
	x = n * m
	powers = len(str(x)) - 1
	for i in range(powers, -1, -1):
		z = 10 ** i
		LCM = lcm(z, n)
		kb = LCM // n
		k = m // kb * kb
		if k:
			print(k * n)
			break


from io import BytesIO, IOBase

def end_zeros(num):
	n = 0
	while num % 10 == 0:
		n += 1
		num = num / 10
	return n

def solve(n, m):
	max_const = 1
	temp = n
	while n % 10 == 0:
		n //= 10
	while n % 2 == 0 and max_const * 5 <= m:
		max_const *= 5
		n //= 2
	while n % 5 == 0 and max_const * 2 <= m:
		max_const *= 2
		n //= 5
	while max_const * 10 <= m:
		max_const *= 10
	return temp * (m // max_const) * max_const
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	print(solve(n, m))


import math
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
data = {'1': '10', '2': '5', '3': '10', '4': '5', '5': '2', '6': '5', '7': '10', '8': '5', '9': '10'}
for _ in range(int(input())):
	(n, k) = invr()
	i = 0
	while True:
		p = str(n)
		if p[-1 - i] == '0':
			i += 1
			continue
		hold = int(data[p[-1 - i]])
		if hold > k:
			n = n * k
			break
		else:
			n = n * hold
			k = k // hold
	print(n)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(cnt_two, cnt_five) = (0, 0)
	n_ = n
	k = 1
	while n_ % 2 == 0:
		cnt_two += 1
		n_ /= 2
	while n_ % 5 == 0:
		cnt_five += 1
		n_ /= 5
	while cnt_two < cnt_five and 2 * k <= m:
		cnt_two += 1
		k *= 2
	while cnt_two > cnt_five and 5 * k <= m:
		cnt_five += 1
		k *= 5
	while k * 10 <= m:
		k *= 10
	k = k * (m // k)
	print(n * k)


def po(n, base):
	out = 0
	while n % base == 0:
		n //= base
		out += 1
	return out

def solve():
	(n, m) = map(int, input().split())
	(po2, po5) = (po(n, 2), po(n, 5))
	for tgt in range(18, 0, -1):
		div = 2 ** max(0, tgt - po2) * 5 ** max(0, tgt - po5)
		mul = m // div * div
		if mul != 0:
			return n * mul
	return n * m
for _ in range(int(input())):
	print(solve())


for tst in range(int(input())):
	(n, m) = map(int, input().split())
	gener = lambda cn1, cn2, k: 2 ** max(0, k - cn1) * 5 ** max(0, k - cn2)
	x1 = 0
	x2 = 0
	n1 = n
	n2 = n
	while n1 % 2 == 0:
		n1 //= 2
		x1 += 1
	while n2 % 5 == 0:
		n2 //= 5
		x2 += 1
	l = 0
	r = 20
	while r - l > 1:
		mid = (r + l) // 2
		x = gener(x1, x2, mid)
		if x <= m:
			l = mid
		else:
			r = mid
	y = gener(x1, x2, l)
	x3 = 1
	for i in range(1, m + 1):
		if i * y <= m:
			x3 = i
		else:
			break
	print(n * y * x3)


from math import gcd

def f(n: int, m: int) -> int:
	for power in reversed(range(0, 20)):
		ten = 10 ** power
		delta = ten // gcd(n, ten)
		if delta <= m:
			return m // delta * delta * n
for _ in range(int(input())):
	print(f(*map(int, input().split())))


def fun(n):
	a = 0
	while n % 10 == 0:
		a += 1
		n /= 10
	return a

def fun2(n):
	a = 0
	while n % 2 == 0:
		a += 1
		n /= 2
	return a

def fun5(n):
	a = 0
	while n % 5 == 0:
		a += 1
		n /= 5
	return a
t = int(input())
for _ in range(t):
	nm = [int(ii) for ii in input().split()]
	(n, m) = (nm[0], nm[1])
	a = fun(n)
	a2 = fun2(n)
	a5 = fun5(n)
	k = 1
	if a5 > a2:
		while m >= k * 2 and a5 > a2:
			k *= 2
			a5 -= 1
	elif a2 > a5:
		while m >= k * 5 and a2 > a5:
			k *= 5
			a2 -= 1
	if k == 1 and m < 10:
		print(n * m)
	else:
		while m >= k * 10:
			k *= 10
		temp = k
		while m >= k + temp:
			k += temp
		print(n * k)


import math
_ = int(input())
for i in range(_):
	z = input().split(' ')
	a = int(z[0])
	cnt = 0
	while a % 10 == 0:
		a /= 10
		a = int(a)
		cnt += 1
	b = int(z[1])
	tmp1 = a
	cnt1 = 0
	cnt3 = 0
	while a % 5 == 0:
		a /= 5
		a = int(a)
		cnt1 += 1
	while a % 2 == 0:
		a /= 2
		a = int(a)
		cnt3 += 1
	if cnt1 == cnt3:
		while b >= 10:
			cnt += 1
			b = math.floor(b / 10)
		print(int(tmp1 * b), end='')
	else:
		if cnt3 == 0:
			t = 1
			for j in range(cnt1):
				t *= 2
				if t > b:
					t /= 2
					break
		else:
			t = 1
			for j in range(cnt3):
				t *= 5
				if t > b:
					t /= 5
					break
		k = math.floor(b / t)
		while k >= 10:
			cnt += 1
			k = math.floor(k / 10)
		print(int(tmp1 * t * k), end='')
	for j in range(cnt):
		print(0, end='')
	print('')


t = int(input())

def gcd(a, b):
	while b:
		temp = a
		a = b
		b = temp % a
	return a
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	ans = n * m
	i = 10 ** 18
	while i >= 10:
		lcm = i * n // gcd(i, n)
		if lcm / n <= m:
			k = lcm // n
			k = m // k
			ans = int(lcm * k)
			break
		i = i // 10
	print(ans)


t = int(input())

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for _ in range(t):
	(n, m) = map(int, input().split())
	res = n * m
	for l in range(20, 0, -1):
		M = 10 ** l
		curr = M // gcd(n, M)
		if curr <= m:
			res = n * curr * int(m // curr)
			break
	print(res)


T = int(input())
mp = {1: 10, 2: 5, 3: 10, 4: 5, 5: 2, 6: 5, 7: 10, 8: 5, 9: 10}

def matsubi(n):
	(d, m) = divmod(n, 10)
	if m != 0:
		return m
	return matsubi(d)
for _ in range(T):
	(N, M) = map(int, input().split())
	while True:
		mt = matsubi(N)
		if mp[mt] <= M:
			N *= mp[mt]
			M //= mp[mt]
		else:
			break
	N *= M
	print(N)


def sol(m, n):
	mod = 10
	num = n
	k = 1
	mult = 1
	counter = 1
	curr = n
	while k <= m:
		if n % mod == 0:
			mult = counter * mult
			mod = mod * 10
			counter = 1
			curr = n
		else:
			k += mult
			counter += 1
			n += num * mult
			if counter * mult > mod:
				if curr == num:
					return num * m
				else:
					multi = (m - k) // mult
					if multi == 0:
						return n
					else:
						return n + num * multi
	return n - mult * num
T = int(input())
for test_case in range(1, T + 1):
	(n, m) = [int(s) for s in input().split(' ')]
	s = sol(m, n)
	print(s)


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a // gcd(a, b) * b
t = int(input())
while t > 0:
	(n, m) = [int(x) for x in input().split()]
	x = n * m
	digs = 0
	while x > 0:
		x = x // 10
		digs += 1
	target = 10 ** digs
	val = -1
	while target > 1:
		fin = lcm(n, target) // n
		if fin > m:
			target = target // 10
		else:
			org_fin = fin
			while fin <= m:
				val = n * fin
				fin = fin + org_fin
			break
	if val == -1:
		print(n * m)
	else:
		print(val)
	t -= 1


def calc(n):
	cnt = 0
	while n:
		if n % 10 == 0:
			cnt += 1
		else:
			break
		n //= 10
	return cnt
t = int(input())
for test in range(t):
	ma = -1
	ans = 0
	(n, m) = map(int, input().split())
	needt = 1
	was = n
	x = n
	cnt1 = 0
	cnt2 = 0
	while x % 2 == 0:
		x //= 2
		cnt1 += 1
	while x % 5 == 0:
		x //= 5
		cnt2 += 1
	if cnt1 > cnt2:
		for b in range(0, 70):
			tmp = 5 ** b
			if tmp > m:
				continue
			ok = str(tmp * n)
			xx = tmp * n
			cnt = calc(xx)
			if cnt > ma:
				ma = cnt
				ans = tmp * n
				needt = tmp
	elif cnt1 < cnt2:
		for b in range(0, 70):
			tmp = 2 ** b
			if tmp > m:
				continue
			ok = str(tmp * n)
			xx = tmp * n
			cnt = calc(xx)
			if cnt > ma:
				ma = cnt
				ans = tmp * n
				needt = tmp
	while needt * 10 <= m and needt:
		needt *= 10
	if needt:
		n *= needt
	l = 1
	r = int(1000000000.0)
	while r - l > 1:
		mid = (l + r) // 2
		if n * mid <= was * m:
			l = mid
		else:
			r = mid
	if n * l <= was * m:
		n *= l
	if calc(n) == 0 or n % was != 0 or n < was:
		print(was * m)
	else:
		print(n)