An architect, Devunky, who lives in Water Deven, has been asked to renovate an old large hospital.

In some countries, people don't want to use numbers that are disliked as numerophobia (4 and 9 are famous in Japan). However, the room numbers in this hospital were numbered from 1 regardless of the number of numerophobia.

Mr. Devunky, who was worried about it, renumbered the room with the numbers excluding "4" and "6", which are the numerophobia of Water Devon, before all the equipment and beds were replaced. However, since the replacement work was planned with the old room number, it is necessary to convert the old room number to the new room number to ensure that the rest of the work is done. Mr. Devunky, who is not good at calculations, is surprised to notice this.

For such Mr. Devunky, please create a program that inputs the old room number and outputs the corresponding new room number.

The correspondence table of room numbers up to the 15th is as follows.

Old room number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15
--- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |- -| --- | --- | ---
New room number | 1 | 2 | 3 | 5 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 15 | 17 | 18 | 19




Input

A sequence of multiple datasets is given as input. The end of the input is indicated by a single line of zeros. For each dataset, the integer n (1 ≤ n ≤ 1,000,000,000) representing the old room number is given on one line.

The number of datasets does not exceed 30000.

Output

Outputs the new room number on one line for each input dataset.

Example

Input

15
100
1000000000
3
0


Output

19
155
9358757000
3

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from sys import stdin
l = stdin.readlines()
for i in l[:-1]:
	print(oct(int(i))[2:].translate(str.maketrans('4567', '5789')))


while True:
	x = int(input())
	if x == 0:
		break
	x = oct(x)[2:]
	print(x.translate(str.maketrans('4567', '5789')))


tbl = ('0', '1', '2', '3', '5', '7', '8', '9')
while 1:
	n = int(input())
	if n == 0:
		break
	s = format(n, 'o')
	ans = ''
	for i in range(len(s)):
		ans += tbl[int(s[i])]
	print(ans)


def testcase_ends():
	n = int(input())
	if n == 0:
		return 1
	n = oct(n)[2:]
	print(*['01235789'[int(i)] for i in n], sep='')
	return 0

def main():
	while not testcase_ends():
		pass
main()


while 1:
	n = int(input())
	if n == 0:
		break
	print(oct(n)[2:].translate(str.maketrans('4567', '5789')))


dic = {'0': '0', '1': '1', '2': '2', '3': '3', '4': '5', '5': '7', '6': '8', '7': '9'}
while 1:
	n = int(input())
	if n == 0:
		break
	s = format(n, 'o')
	ans = ''
	for i in range(len(s)):
		ans += dic[s[i]]
	print(ans)


import sys

def convert(dec):
	s = ''
	d = dec
	while True:
		div = d // 8
		rem = d % 8
		d = div
		if rem == 4:
			rem = 5
		elif rem == 5:
			rem = 7
		elif rem == 6:
			rem = 8
		elif rem == 7:
			rem = 9
		s = str(rem) + s
		if div <= 0:
			break
	return s
for s in sys.stdin:
	if int(s) == 0:
		break
	print(convert(int(s)))


while True:
	n = int(input())
	if n == 0:
		break
	print(str(oct(n)[2:]).translate(str.maketrans('4567', '5789')))


dic = {'0': '0', '1': '1', '2': '2', '3': '3', '4': '5', '5': '7', '6': '8', '7': '9'}
while 1:
	n = int(input())
	if n == 0:
		break
	s = list(format(n, 'o'))
	for i in range(len(s)):
		s[i] = dic[s[i]]
	print(*s, sep='')


a = '0 1 2 3 5 7 8 9'.split()
while True:
	N = int(input())
	if N == 0:
		break
	print(''.join((a[int(n)] for n in oct(N)[2:])))


def base10to8(n):
	ans = ''
	while n > 0:
		ans = str(n % 8) + ans
		n = n // 8
	return ans
while True:
	n = int(input())
	if n == 0:
		break
	s = base10to8(n)
	table = [0, 1, 2, 3, 5, 7, 8, 9]
	for i in range(len(s)):
		print(table[int(s[i])], end='')
	print('')


from sys import stdin
readline = stdin.readline
while True:
	old_room_num = int(readline())
	if old_room_num == 0:
		break
	octal = oct(old_room_num)[2:]
	new_room_num = octal.translate(str.maketrans('4567', '5789'))
	print(new_room_num)


def testcase_ends():
	n = int(input())
	if n == 0:
		return 1
	n = oct(n)[2:]
	n = n.replace('7', '9')
	n = n.replace('6', '8')
	n = n.replace('5', '7')
	n = n.replace('4', '5')
	print(n)
	return 0

def main():
	while not testcase_ends():
		pass
main()


while True:
	n = int(input())
	if not n:
		break
	n = oct(n)[2:]
	print(n.translate(str.maketrans('4567', '5789')))


import sys
from sys import stdin
from bisect import bisect_left
input = stdin.readline

def solve(num):
	ans = []
	o_txt = oct(num)[2:]
	for o in o_txt:
		if int(o) >= 6:
			ans.append(int(o) + 2)
		elif int(o) == 5:
			ans.append(7)
		elif int(o) >= 4:
			ans.append(int(o) + 1)
		else:
			ans.append(int(o))
	return ans

def main(args):
	while True:
		num = int(input())
		if num == 0:
			break
		ans = solve(num)
		print(*ans, sep='')
main(sys.argv[1:])


while True:
	n = int(input())
	if n == 0:
		break
	n = oct(n)[2:]
	print(n.translate(str.maketrans('4567', '5789')))


from sys import stdin
while True:
	n = int(stdin.readline())
	if not n:
		break
	print(str(oct(n))[2:].translate(str.maketrans('4567', '5789')))


while True:
	a = int(input())
	if a == 0:
		break
	ans = oct(a)[2:]
	print(ans.translate(str.maketrans({'4': '5', '5': '7', '6': '8', '7': '9'})))


while 1:
	n = int(input())
	if not n:
		break
	print(''.join(('01235789'[int(i)] for i in oct(n)[2:])))


while 4:
	n = int(input())
	if n == 0:
		break
	print(oct(n)[2:].translate(str.maketrans('4567', '5789')))


a = {'0': '0', '1': '1', '2': '2', '3': '3', '4': '5', '5': '7', '6': '8', '7': '9'}
while True:
	n = int(input())
	if n == 0:
		break
	else:
		N = list(format(n, 'o'))
	for i in range(len(N)):
		print(a[N[i]], end='')
	print()


while True:
	n = int(input())
	if n == 0:
		break
	print(''.join(('01235789'[int(i)] for i in oct(n)[2:])))


print(*[''.join(('01235789'[int(i)] for i in oct(int(x))[2:])) for x in open(0).read().split()[:-1]], sep='\n')


def ge(arr):
	for i in range(len(arr)):
		tmp = int(arr[i])
		if tmp >= 4:
			tmp += 1
		if tmp >= 6:
			tmp += 1
		arr[i] = str(tmp)
	return arr
while True:
	n = int(input())
	if n == 0:
		break
	print(''.join(ge(list(oct(n))[2:])))


octD = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 5, '5': 7, '6': 8, '7': 9}
while True:
	n = int(input())
	if n == 0:
		break
	else:
		N = list(format(n, 'o'))
		for i in range(len(N)):
			print(octD[N[i]], end='')
		print()


def x(i):
	if i == 0:
		return 0
	if i == 1:
		return 1
	if i == 2:
		return 2
	if i == 3:
		return 3
	if i == 4:
		return 5
	if i == 5:
		return 7
	if i == 6:
		return 8
	if i == 7:
		return 9
while True:
	n = int(input())
	if n == 0:
		break
	n = oct(n)
	n = list(n)
	del n[0:2]
	for i in range(len(n)):
		print(x(int(n[i])), end='')
	print()


import sys, math, os
PYDEV = os.environ.get('PYDEV')
if PYDEV == 'True':
	sys.stdin = open('sample-input.txt', 'rt')
while True:
	n = int(input())
	if n == 0:
		break
	print(oct(n)[2:].replace('7', '9').replace('6', '8').replace('5', '7').replace('4', '5'))


import sys
l = sys.stdin.readlines()
for i in l[:-1]:
	print(oct(int(i))[2:].translate(str.maketrans('4567', '5789')))


from sys import stdin
line = stdin.readlines()
for i in line[:-1]:
	print(oct(int(i))[2:].translate(str.maketrans('4567', '5789')))


while 1:
	c = input()
	if c == '0':
		break
	print(format(int(c), 'o').translate(str.maketrans({'4': '5', '5': '7', '6': '8', '7': '9'})))


def main():
	while True:
		num = int(input())
		if num == 0:
			break
		num = str(oct(num)[2:])
		ans = num.translate(str.maketrans('4567', '5789'))
		print(ans)
main()


while 1:
	n = int(input())
	if n == 0:
		break
	n = str(oct(n)[2:])
	n = n.translate(str.maketrans('4567', '5789'))
	print(n)


dic = {'0': '0', '1': '1', '2': '2', '3': '3', '4': '5', '5': '7', '6': '8', '7': '9'}

def trans(n):
	if n == 0:
		return '0'
	acc = ''
	while n:
		acc += dic[str(n % 8)]
		n //= 8
	return acc[::-1]
while True:
	n = int(input())
	if n == 0:
		break
	print(trans(n))