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

Background

由于小鳄鱼打羽毛球总是输给wyy，于是他非常想赢一局，直到在一次惜败中喊出了那句“四舍五入我就赢了”。

Description

给定一个自然数 x 。您可以进行以下运算：

• 选择一个正整数 k ，并将 x 四舍五入到第 k 位 。

请注意，位置是从 0 开始从右向左编号的。如果数字有 k 位，则认为 k-th位置的数字等于 0 。

四舍五入的方法如下

• 如果 (k−1)-th位置的数字大于或等于 5 ，那么 k-th位置的数字增加 1 ，否则 k /th位置的数字保持不变(使用数学四舍五入)。
• 如果在运算之前， k-th 位置上的数字是 9 ，并且应该增加 1 ，那么我们搜索 k′-th 位置上的数字小于 9 的最小位置 k′ ( k′>k )，并在 k′-th 位置上的数字上加上 1 。然后我们赋值 k=k′ 。
• 之后，所有位置小于 k 的数字都被替换为零。

你的任务是尽可能地将 x 变大，如果你可以多次执行这个操作的话。

例如，如果 x 等于 3451 ，那么如果连续选择

• k=1 ，那么操作后 x 将变为 3450 。
• k=2 ，那么操作后 x 将变为 3500
• k=3 ，然后经过运算 x 将变成 4000 。
• k=4 ，然后经过运算后 x 将变为 0

要使答案最大化，需要先选择 k=2 ，然后选择 k =3，那么数字就会变成 4000 。

Input

第一行包含一个整数 t ( 1≤t≤1e4 ) - 测试用例数。

每个测试用例由长度不超过 2e5 的正整数 x 组成。保证整数中没有前导零。

保证所有测试用例中所有整数 x 的长度总和不超过 2e5 。

Output

对每组输入数据进行运算后，输出 x 的最大可能值。

Samples

2
5
2045

10
2100

Limitation

1s, 1024KiB for each test case.