令 $(_w$ 和 $)_w$ 为权重为 $w$ 的圆括号。定义平衡加权括号序列（BWBS）如下：

• 空序列是 BWBS。
• 如果 $P$ 是一个 BWBS，那么 $(_w P )_w$ 也是一个 BWBS。即，开头和结尾的两个括号具有相同的权重。
• 如果 $P$ 和 $Q$ 都是 BWBS，那么 $PQ$ 也是一个 BWBS。

例如，$(_1(_3)_3)_1$ 和 $(_5(_7)_7(_2)_2)_5$ 都是 BWBS，而 $(_1(_3)_1)_3$ 和 $)_5(_5(_7)_7$ 则不是。

考虑一个没有前导零的 $n$ 位正整数，其第 $i$ 位（从高位起）数字为 $d_i$（即该整数等于 $\sum_{i=1}^{n} d_i \times 10^{n-i}$）。如果存在一个平衡加权括号序列，使得第 $i$ 个括号的权重为 $d_i$，则称该整数为括号整数。例如，1000022122 是一个括号整数，因为存在这样的 BWBS $(_1(_0(_0)_0)_0(_2)_2)_1(_2)_2$。

给定一个整数 $A$，求小于或等于 $A$ 的最大括号整数。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $A$ ($11 \le A < 10^{2 \times 10^5}$)。

保证所有测试数据中 $A$ 的总位数不超过 $2 \times 10^5$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示小于或等于 $A$ 的最大括号整数。由于 11 是一个括号整数，因此答案一定存在。注意，括号整数不能有前导零。

样例

输入 1

4
20250525
11451419198100
1001
1000

输出 1

20244202
11451418814154
1001
99