题目描述

星港调度中心有一台很旧的回执机。它接到编号 $x$ 后，会按一条固定规则生成最终回执编号。

这台机器的规则如下：

值班员每天会收到大量查询。虽然规则看上去像递归套递归，但调度系统要求你必须快速给出每个编号的回执结果。

给定若干个正整数 $x$，请分别输出 $f(x)$ 的值。输入以 $0$ 结束，结束标记不需要处理。

输入格式

在文件 starport_receipt.in 中读入。 输入包含若干行，最多若干行。 每行一个正整数 $x$，满足 $x \le 1000000$。 最后一行为 $0$，表示输入结束。

输出格式

在文件 starport_receipt.out 中输出。 对每个需要查询的 $x$，输出一行一个整数，表示 $f(x)$。

样例

输入数据1

111
101
0

输出数据1

101
91

提示

数据范围

• 对于30%的数据，$x \ge 101$。
• 另有40%的数据，$x \le 100$。
• 对于100%的数据，$1 \le x \le 1000000$，查询数量不超过2500000。