该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

琪露诺的外号是 “笨蛋⑨”，虽然听起来不怎么好听，但是自从有了这个外号后，琪露诺就一直把 $9$ 这个数字当作自己的幸运数字。

题目描述

琪露诺开学了，新的学期被分配到了一个新的学号 $N$（学号均为数字组成，且没有前导 $0$）。但是琪露诺不喜欢这个数字。于是向学院院长魔理沙申请换一个学号。

但是院长不打算这么轻易的答应，提出了一个要求：琪露诺允许在学号 $N$ 的任意位置插入一个 $0 \sim 9$ 之间的数字，使学号变成 $9$ 的倍数，而且必须是通过该操作能得到的最小的数字（不允许前导 $0$）。如果琪露诺不能找出正确答案，就不允许改学号。

琪露诺的外号 “笨蛋⑨” 不是没有原因的，显然没办法自己解决这个问题。快帮帮它吧~

输入格式

第一行一个整数 $T$，表示数据组数。每组数据格式如下：

只有一行，一个整数 $N$，表示琪露诺的新学号。

输出格式

$T$ 行，每行对应一组数据的答案

测试样例

4
5
33
12121
18

45
333
121212
108

样例解释

样例一说明

第一组数据，数字 $5$ 加上一位数字，满足 $9$ 倍数的只有 $45$ 和 $54$，显然 $45$ 是所有可组成的数中最小的。

第二组数据，只有 $333$ 符合要求。

第三组数据，数字 $12121$ 加上一位数字，满足 $9$ 倍数的有 $212121、122121、121221、121212$，其中 $121212$ 是所有可组成的数中最小的。

第四组数据，虽然 $18$ 本身是 $9$ 的倍数，但按题意必须插入 $1$ 位数字（且不能有前导 $0$）；在可组成的所有 $9$ 的倍数中，$108$ 是最小的。

数据范围

对于所有的数据，有 $1 \le T \le 100，1 \le N \le 10^{123456}$。