题目描述

校园科创节推出了趣味闯关游戏「数字转转转」，小珅和小泽组队参与挑战。游戏设置了多轮数字变换关卡，每一轮都要按照固定规则对数字进行迭代操作，两人需要根据每一个数字指定的操作次数，算出最终变换结果，才能顺利通关拿到奖励，现在请你协助他们完成关卡计算任务。

游戏的操作规则如下： 初始给定一个正整数 $x$，将它每一位上的数字相加得到一个新数，这样完整完成一轮变化的过程，就被称为一次「数字转转转」操作。

举个操作示例，初始数字 $x=375$：

• 进行一次「数字转转转」：$375$ 变为 $3+7+5=15$；
• 进行二次「数字转转转」：$15$ 变为 $1+5=6$；
• 进行三次「数字转转转」：$6$ 各位相加仍为 $6$，后续再进行任意次数操作结果都不会再改变。

本次关卡需要处理 $n$ 个数字，范围是从 $1$ 到 $n$，每个数字都有专属的操作次数要求。请你依次算出数字 $i$ 执行 $a_i$ 次「数字转转转」之后最终得到的数值。

输入格式

输入共两行。

第一行一个整数 $n$，表示你要处理 $1 \sim n$ 这 $n$ 个数；
第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n$，第 $i$ 个表示数字 $i$ 要做多少次“数字转转转”。

输出格式

输出一行 $n$ 个整数，第 $i$ 个表示数字 $i$ 做 $a_i$ 次“数字转转转”后得到的结果。

输入输出样例

11
1 3 2 1 99 100 93 57 18 2 1

1 2 3 4 5 6 7 8 9 1 2

20
3 10 4 1 6 7 2 6 3 9 3 4 4 1 3 6 7 7 2 7

1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2

说明/提示

样例 1 解释

• 对于前 $1 \sim 9$，无论做多少次“数字转转转”，它们始终都是它们本身；
• 对于 $10$，其做第 $1$ 次“数字转转转”后变为 $1 + 0 = 1$，第二次后变为 $1 = 1$；
• 对于 $11$，其做第 $1$ 次“数字转转转”后变为 $1 + 1 = 2$。

数据规模与约定

本题共 $10$ 个测试点。对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^9$；

1
814671370

1