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}\)