Background

Special for beginners, ^_^

Description

话说M国有个丞相特别喜欢说666，在他的带动下，每次上朝，国王让大臣们发表意见，大臣们都会说666，最后把皇帝听烦了，于是规定全国范围内禁止说和使用6。那么问题来了：在现在禁止使用6（5后面直接跳到7）的计数系统下，某个数等价于标准十进制的几？

Format

Input

第一行为一个整数 $T (1 \le T \le 10 ^ 6)$，代表数据组数。

第二行至第 T + 1 行每行包含一个正整数 $x_i（\le 10 ^ {19}）$，表示M国的数字。 .

Output

输出共 N 行。 第 i 行表示 $x_i$ 实际上对应的数字。

Samples

2
1
17

1
15

Limitation

1s, 1024KiB for each test case.