You are given an integer $n$. You have to change the minimum number of digits in it in such a way that the resulting number does not have any leading zeroes and is divisible by $7$.

If there are multiple ways to do it, print any of them. If the given number is already divisible by $7$, leave it unchanged.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 990$) — the number of test cases.

Then the test cases follow, each test case consists of one line containing one integer $n$ ($10 \le n \le 999$).


-----Output-----

For each test case, print one integer without any leading zeroes — the result of your changes (i. e. the integer that is divisible by $7$ and can be obtained by changing the minimum possible number of digits in $n$).

If there are multiple ways to apply changes, print any resulting number. If the given number is already divisible by $7$, just print it.


-----Examples-----

Input
3
42
23
377
Output
42
28
777


-----Note-----

In the first test case of the example, $42$ is already divisible by $7$, so there's no need to change it.

In the second test case of the example, there are multiple answers — $28$, $21$ or $63$.

In the third test case of the example, other possible answers are $357$, $371$ and $378$. Note that you cannot print $077$ or $77$.

Difficulty: EASY
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	if n % 7 == 0:
		print(n)
	else:
		x = n % 7
		y = n % 10
		if y + (7 - x) <= 9:
			print(n + (7 - x))
		else:
			print(n - x)


for _ in range(int(input())):
	n = int(input())
	if n % 7 == 0:
		print(n)
	else:
		num = n % 7
		x = abs(7 - num)
		if n % 10 + x < 10:
			print(n + x)
		else:
			print(n - num)


import sys

def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		x = int(sys.stdin.readline())
		y = 7 - x % 7
		if y != 7:
			if int(str(x)[-1]) + y > 9:
				x = x - (7 - y)
			else:
				x = x + y
		print(x)
main()


t = int(input())
for i in range(t):
	a = int(input())
	r = a % 7
	r_10 = a % 10
	if a % 7 == 0:
		print(a)
	elif r_10 + 7 - r >= 10:
		print(a - r)
	elif a + 7 - r > 10:
		print(a + 7 - r)
	else:
		print(a + 14 - r)


def processing(n):
	if n % 7 == 0:
		return n
	else:
		k = n % 7
		temp_data = 7 - k
		if n % 10 + temp_data < 10:
			return n + temp_data
		else:
			return n - k
t = int(input())
while t > 0:
	n = int(input())
	print(processing(n))
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 7 == 0:
		print(n)
		continue
	p1 = n // 7 * 7
	p2 = (n // 7 + 1) * 7
	d = p2 // 10
	if n >= d * 10:
		print(p2)
	else:
		print(p1)


for caseno in range(int(input())):
	n = int(input())
	r = n % 7
	dr = 7 - r
	u = n % 10
	answer = max(7, n)
	if r == 0:
		print(answer)
		continue
	if u + dr < 10:
		answer = n + dr
	else:
		answer = n - r
	print(answer)


test = int(input())
for i in range(test):
	n = int(input())
	if n % 7 == 0:
		print(n)
	else:
		hig = (int(n / 7) + 1) * 7
		lo = int(n / 7) * 7
		if len(str(n)) == 1:
			print(7)
		elif len(str(n)) == 2:
			h = str(hig)
			l = str(lo)
			k = str(n)
			if h[0] == k[0]:
				print(hig)
			else:
				print(lo)
		else:
			h = str(hig)
			l = str(lo)
			k = str(n)
			if h[0] == k[0] and h[1] == k[1]:
				print(hig)
			else:
				print(lo)


t = int(input())
while t:
	t -= 1
	n = int(input())
	i = n
	if n % 7 == 0:
		print(n)
	else:
		n = n + (7 - n % 7)
		if int(n / 10) - int(i / 10) > 0:
			n -= 7
		print(n)


for _ in range(int(input())):
	n = int(input())
	a = n + (7 - n % 7)
	b = n - n % 7
	if n % 7 == 0:
		print(n)
	else:
		print(a if int(a / 10) == int(n / 10) else b)


t = int(input())
for i in range(t):
	n = int(input())
	if n % 7 == 0:
		print(n)
	else:
		ans = -1
		for j in range(10):
			if (n - n % 10 + j) % 7 == 0:
				ans = n - n % 10 + j
		print(ans)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	x = n % 7
	y = n // 10
	z = (n - x + 7) // 10
	o = (n - x) // 10
	if x == 0:
		print(n)
	elif y == z:
		print(n - x + 7)
	else:
		print(n - x)


z = int(input())
for q in range(z):
	a = int(input())
	k = a % 7
	if k == 0:
		print(a)
		continue
	c = a % 10 + 7 - a % 7
	c1 = a - a % 7
	c3 = a + 7 - a % 7
	if 9 < c:
		print(c1)
	else:
		print(c3)


import sys
from math import *
from math import *
from functools import *
t = int(input())
for _ in range(t):
	n = int(input())
	a = b = 0
	for i in range(7):
		if (n + i) % 7 == 0:
			a = n + i
		if (n - i) % 7 == 0:
			b = n - i
	print(a) if a < n + (10 - n % 10) else print(b)


for _ in range(int(input())):
	n = int(input())
	if n % 7 == 0:
		print(n)
	else:
		r = n % 7
		if n % 10 + 7 - r < 10:
			print(n + 7 - r)
		else:
			print(n - r)