给定一个仅由数字 构成的字符串 。一次操作可按如下方式进行： 从 中选择既不是最左端字符也不为 的某一字符； 将该字符的数值减少 ； 随后把它与左侧相邻字符交换位置。 例如，字符串 经过一次操作可以变成 或 。 你可以不限次数地执行上述操作。请计算能够得到的字典序最大的字符串，并输出该字符串。

输入描述:

第一行输入一个整数 ，表示测试用例数量。此后 行，每行输入一个不含前导零的数字字符串 ，满足 。保证所有测试用例的 之和不超过 。

输出描述:

对于每个测试用例，在一行上输出通过任意次数操作后能够得到的字典序最大的字符串。