Divide the digits
82% Success2400 Attempts10 Points1s Time Limit256MB Memory1024 KB Max Code

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

Examples
Input
2
1321
42255
Output
25
270
Explanation

For the first test case:

  • Minimum possible sum is \(25\), which can be achieved if \(X = 12, \ Y = 13\).

For the second test case:

  • Minimum possible sum is \(270\), which can be achieved if \(X = 245, \ Y = 25\).

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...
Results