← 返回题目列表

Codeforces · 2204/E

E. 数字总和(再次)

中文机器翻译题面 查看原题

对于正整数(严格大于 $$$0$$$)$$$x$$$,字符串 $$$S(x)$$$ 通过以下过程形成:

  1. 最初,该字符串为空;
  2. 然后,将不带前导零的数字 $$$x$$$ 的十进制表示形式附加到其右侧;
  3. 之后,如果$$$x \le 9$$$,则过程结束。否则,将$$$x$$$替换为$$$x$$$的各位数字之和,并返回步骤$$$2$$$;

例如:

  • $$$S(75)$$$ 是 75123;
  • $$$S(30)$$$ 是 303;
  • $$$S(9)$$$ 是 9.

给你一个由数字组成的字符串 $$$s$$$。您的任务是重新排列该字符串中的字符,使其形成某个数字 $$$x$$$ 的字符串 $$$S(x)$$$。不允许删除字符和/或添加新字符。如果给定的字符串 $$$s$$$ 已经是某个数字 $$$x$$$ 的字符串 $$$S(x)$$$,则可以将其保持不变。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由一个字符串组成,其中包含 $$$s$$$ ($$$1 \le |s| \le 10^5$$$) — 一系列数字。

输入的附加限制:

  • 所有测试用例$$$s$$$的长度总和不超过$$$10^5$$$;
  • 可以重新排列 $$$s$$$ 中的数字以获得某个正整数 $$$x$$$ 的 $$$S(x)$$$。

输出

对于每个测试用例,重新排列字符后输出一个字符串 - $$$s$$$。如果有多个有效答案,则输出其中任何一个。

示例

输入
复制

5
12735
1
011
99999299999999299959999999999999
4621467

输出
复制

75123
1
101
99999999999999999999999999992529
6442167