#include <bits/stdc++.h>
#pragma gcc optimize(2)
#pragma warning(disable : 4996)
using namespace std;
long long gcd(long long m, long long n) { return n ? gcd(n, m % n) : m; }
long long pail(long long m) {
  long long sum = 0;
  long long n = m;
  while (m) {
    sum = sum * 10 + m % 10;
    m /= 10;
  }
  if (n == sum)
    return 1;
  else
    return 0;
}
long long prime(long long n) {
  int f = 0;
  for (long long i = 2; i <= sqrt(n * 1.0); ++i) {
    if (n % i == 0) {
      f = 1;
      return 1;
    }
  }
  if (n == 1 || n == 2) return 0;
  if (f == 0) return 0;
}
void quick_sort(int q[], int l, int r) {
  if (l >= r) return;
  int i = l - 1, j = r + 1, x = q[l + r >> 1];
  while (i < j) {
    do i++;
    while (q[i] < x);
    do j--;
    while (q[j] > x);
    if (i < j) swap(q[i], q[j]);
  }
  quick_sort(q, l, j);
  quick_sort(q, j + 1, r);
}
bool cmp(int a, int b) { return a > b; }
int binpow(int a, int b) {
  int prod = 1;
  a = a % 9901;
  while (b) {
    if (b & 1) prod = prod % 9901 * a % 9901;
    b >>= 1;
    a = a % 9901 * a % 9901;
  }
  return prod;
}
int sum(int p, int c) {
  if (c == 0) return 1;
  if (c % 2 == 0) return (p % 9901 * sum(p, c - 1) + 1) % 9901;
  return (1 + binpow(p, c / 2 + 1)) * sum(p, c / 2) % 9901;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    int s;
    cin >> s;
    int m = 0;
    int cnt = s;
    while (s >= 10) {
      m = s / 10;
      cnt += m;
      s = s % 10 + m;
    }
    cout << cnt << endl;
  }
}

### Prompt

Generate a CPP solution to the following problem:

Mishka wants to buy some food in the nearby shop. Initially, he has s burles on his card. 

Mishka can perform the following operation any number of times (possibly, zero): choose some positive integer number 1 ≤ x ≤ s, buy food that costs exactly x burles and obtain ⌊x/10⌋ burles as a cashback (in other words, Mishka spends x burles and obtains ⌊x/10⌋ back). The operation ⌊a/b⌋ means a divided by b rounded down.

It is guaranteed that you can always buy some food that costs x for any possible value of x.

Your task is to say the maximum number of burles Mishka can spend if he buys food optimally.

For example, if Mishka has s=19 burles then the maximum number of burles he can spend is 21. Firstly, he can spend x=10 burles, obtain 1 burle as a cashback. Now he has s=10 burles, so can spend x=10 burles, obtain 1 burle as a cashback and spend it too.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases.

The next t lines describe test cases. Each test case is given on a separate line and consists of one integer s (1 ≤ s ≤ 10^9) — the number of burles Mishka initially has.

Output

For each test case print the answer on it — the maximum number of burles Mishka can spend if he buys food optimally.

Example

Input


6
1
10
19
9876
12345
1000000000


Output


1
11
21
10973
13716
1111111111

### Response

```cpp
#include <bits/stdc++.h>
#pragma gcc optimize(2)
#pragma warning(disable : 4996)
using namespace std;
long long gcd(long long m, long long n) { return n ? gcd(n, m % n) : m; }
long long pail(long long m) {
  long long sum = 0;
  long long n = m;
  while (m) {
    sum = sum * 10 + m % 10;
    m /= 10;
  }
  if (n == sum)
    return 1;
  else
    return 0;
}
long long prime(long long n) {
  int f = 0;
  for (long long i = 2; i <= sqrt(n * 1.0); ++i) {
    if (n % i == 0) {
      f = 1;
      return 1;
    }
  }
  if (n == 1 || n == 2) return 0;
  if (f == 0) return 0;
}
void quick_sort(int q[], int l, int r) {
  if (l >= r) return;
  int i = l - 1, j = r + 1, x = q[l + r >> 1];
  while (i < j) {
    do i++;
    while (q[i] < x);
    do j--;
    while (q[j] > x);
    if (i < j) swap(q[i], q[j]);
  }
  quick_sort(q, l, j);
  quick_sort(q, j + 1, r);
}
bool cmp(int a, int b) { return a > b; }
int binpow(int a, int b) {
  int prod = 1;
  a = a % 9901;
  while (b) {
    if (b & 1) prod = prod % 9901 * a % 9901;
    b >>= 1;
    a = a % 9901 * a % 9901;
  }
  return prod;
}
int sum(int p, int c) {
  if (c == 0) return 1;
  if (c % 2 == 0) return (p % 9901 * sum(p, c - 1) + 1) % 9901;
  return (1 + binpow(p, c / 2 + 1)) * sum(p, c / 2) % 9901;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    int s;
    cin >> s;
    int m = 0;
    int cnt = s;
    while (s >= 10) {
      m = s / 10;
      cnt += m;
      s = s % 10 + m;
    }
    cout << cnt << endl;
  }
}

```