You are given a number $N$. 

You are required to form two numbers $X$ and $Y$ such that:

• The sum of frequency of each digit in $X$ and $Y$ is equal to frequency of that digit in $N$.
• The sum of numbers $X$ and $Y$ must be minimum.

Your task is to determine the minimum possible sum of $X$ and $Y$.

Input format

• The first line contains an integer $T$ that denotes the number of test cases.
• For each test case:
  • The first line contains an integer $N$.

Output format

For each test case, you are required to print the minimum possible sum of $X$ and $Y$ in a new line.

Constraints

$1 \le T \le 10^5 \\ 10 \le N \le 2 \times 10^{18}$