We call a positive integer number fair if it is divisible by each of its nonzero digits. For example, $102$ is fair (because it is divisible by $1$ and $2$), but $282$ is not, because it isn't divisible by $8$. Given a positive integer $n$. Find the minimum integer $x$, such that $n \leq x$ and $x$ is fair.


-----Input-----

The first line contains number of test cases $t$ ($1 \leq t \leq 10^3$). Each of the next $t$ lines contains an integer $n$ ($1 \leq n \leq 10^{18}$).


-----Output-----

For each of $t$ test cases print a single integer — the least fair number, which is not less than $n$.


-----Examples-----

Input
4
1
282
1234567890
1000000000000000000
Output
1
288
1234568040
1000000000000000000


-----Note-----

Explanations for some test cases:

In the first test case number $1$ is fair itself.

In the second test case number $288$ is fair (it's divisible by both $2$ and $8$). None of the numbers from $[282, 287]$ is fair, because, for example, none of them is divisible by $8$.

Difficulty: EASY
Tags: Number theory

Complete search
Skill types: Complete search

Starter code:

Solutions:
import math

def lcm(lista):
	k = 1
	for i in lista:
		if i != 0:
			k = k * i // math.gcd(k, i)
	return k

def lyans():
	a = input()
	listn = []
	for i in a:
		listn.append(int(i))
	n = len(listn)
	for i in range(len(a)):
		l = lcm(listn[:n - i - 1])
		nb = int(a[n - i - 1:])
		if i == len(a) - 1:
			star = int(a)
		elif int(a) % l == 0:
			star = nb
		else:
			temp = l - int(a) % l
			star = temp + nb
		for m in range(star, 10 ** (i + 1), l):
			lsm = [int(i) for i in str(m)]
			lsm.append(l)
			lm = lcm(lsm)
			last = int(a[:n - i - 1] + '0' * (i + 1 - len(str(m))) + str(m))
			if last % lm == 0:
				return last
t = int(input())
for ti in range(t):
	print(lyans())


def gcd(a, b):
	while a and b:
		if a > b:
			a %= b
		else:
			b %= a
	return a + b

def check(n):
	s = str(n)
	nok = 1
	for elem in s:
		if elem != '0':
			nok = nok * int(elem) // gcd(nok, int(elem))
	return n % nok == 0
t = int(input())
for _ in range(t):
	n = int(input())
	for i in range(20):
		nn = n
		if i == 0:
			cur_s = str(n)
		elif i >= len(str(n)):
			cur_s = '0'
		else:
			cur_s = str(n)[:-i]
		st10 = 10 ** i
		nok = 1
		for elem in cur_s:
			if elem != '0':
				nok = nok * int(elem) // gcd(nok, int(elem))
		if i == 0 and n % nok == 0:
			print(n)
			break
		diff = nok - n % nok
		n += diff
		while str(n // st10) == cur_s and (not check(n)):
			n += nok
		if str(n // st10) == cur_s and check(n):
			print(n)
			break
		n = nn


def checkFair(num):
	temp = num
	while temp != 0:
		mod = temp % 10
		if mod != 0:
			if num % mod != 0:
				return False
		temp = temp // 10
	return True
dic = {}
for _ in range(int(input())):
	num = int(input())
	flag = checkFair(num)
	if flag:
		print(num)
	else:
		temp = num
		if dic.get(num, -1) != -1:
			print(dic[temp])
		else:
			while not flag:
				flag = checkFair(num)
				if flag:
					dic[temp] = num
					print(num)
				num += 1


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log, ceil
from collections import defaultdict as dd
from collections import Counter as cc
from bisect import bisect_left as bl
from bisect import bisect_right as br
import functools
sys.setrecursionlimit(100000000)
intinp = lambda : int(input().strip())
stripinp = lambda : input().strip()
fltarr = lambda : list(map(float, input().strip().split()))
intarr = lambda : list(map(int, input().strip().split()))
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
MOD = 1000000007
num_cases = intinp()
seen = {}

@functools.lru_cache(None)
def check(num):
	for v in set(str(num)):
		v = int(v)
		if v != 0 and num % v:
			return False
	return True
for _ in range(num_cases):
	n = intinp()
	y = n
	if n in seen:
		print(seen[n])
		continue
	while not check(n):
		n += 1
	print(n)
	seen[y] = n