for _ in range(int(input())):
  print(''.join(sorted(input())))

for _ in range(int(input())):
  x = [ord(c) - ord('0') for c in input()]
  n = len(x)
  for i in range(n - 2, -1, -1):
    if x[i] + x[i + 1] >= 10:
      x[i + 1] += x[i] - 10
      x[i] = 1
      break
  else:
    x[1] += x[0]
    x.pop(0)
  print(''.join([chr(c + ord('0')) for c in x]))

for _ in range(int(input())):
  n = int(input())
  k = list(map(int, input().split()))
  h = list(map(int, input().split()))
  st = []
  for i in range(n):
    st.append([k[i] - h[i], k[i]])
  st.sort()
  l, r = -1, -1
  ans = 0
  for it in st:
    if it[0] >= r:
      ans += (r - l) * (r - l + 1) // 2
      l, r = it
    else:
      r = max(r, it[1])
  ans += (r - l) * (r - l + 1) // 2
  print(ans)

calc = 1
nxt = [1, 0]

for _ in range(int(input())):
  n = int(input())
  a = sorted(list(map(int, input().split())))
  while calc <= n:
    for i in range(calc):
      nxt.append(calc - i - 1)
    calc *= 2
  left = []
  for i in range(n + 1):
    if i == 0 or i == n or a[i] != a[i - 1]:
      left.append(i)
    else:
      left.append(left[-1])
  mid = 1
  ans = n + 2
  while mid <= n:
    for len1 in range(n + 1):
      if left[len1] == len1:
        len2 = left[min(n, len1 + mid)] - len1
        len3 = n - len1 - len2
        ans = min(ans, nxt[len1] + (mid - len2) + nxt[len3])
    mid *= 2
  print(ans)

#include<bits/stdc++.h>

using namespace std;

const int N = 300043;

vector<int> g[N];
int cnt[N];
int c[N];
vector<int> g2[N];
int par[N];
int used[N];

void dfs(int x, int p = -1)
{
    par[x] = p;
    for(auto y : g[x])
        if(y != p)
        {
            dfs(y, x);
            cnt[x] += cnt[y];
        }
    cnt[x] += c[x];
}   

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &c[i]);
    for(int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(0);
    for(int i = 0; i < n; i++)
        for(auto j : g[i])
        {
            if(i == par[j])
            {
                if(c[i] == 1 || cnt[0] - cnt[j] > 1)
                    g2[i].push_back(j);
            }
            else
            {
                if(c[i] == 1 || cnt[i] > 1)
                    g2[i].push_back(j);
            }
        }
    queue<int> q;
    for(int i = 0; i < n; i++)
    {
        if(c[i] == 1)
        {
            q.push(i);
            used[i] = 1;
        }
    }
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        for(auto y : g2[k])
            if(used[y] == 0)
            {
                used[y] = 1;
                q.push(y);
            }
    }
    for(int i = 0; i < n; i++)
        printf("%d ", used[i]);
    puts("");
}

#include <bits/stdc++.h>     

using namespace std;

const int MOD = 998244353;
const int L = 720720;

int add(int x, int y, int m = MOD)
{
    x += y;
    if(x >= m) x -= m;
    return x;
}

int mul(int x, int y, int m = MOD)
{
    return (x * 1ll * y) % m;
}

int binpow(int x, int y)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}

int inv(int x)
{
    return binpow(x, MOD - 2);
}

int divide(int x, int y)
{
    return mul(x, inv(y));
}

int main()
{
    int n, a0, x, y, k, M;
    cin >> n >> a0 >> x >> y >> k >> M;
    vector<int> arr(n);
    arr[0] = a0;
    for(int i = 1; i < n; i++)
        arr[i] = add(mul(arr[i - 1], x, M), y, M);
    int ans = 0;
    int total_ways = binpow(n, k);
    int coeff = mul(divide(total_ways, n), k);
    vector<vector<int>> dp(k, vector<int>(L));
    for(int i = 0; i < n; i++)
    {
        int p = arr[i] / L;
        int q = arr[i] % L;
        dp[0][q]++;
        ans = add(ans, mul(p, mul(L, coeff)));
    }
    int cur_coeff = divide(total_ways, n);
    for(int i = 1; i <= k; i++)
    {
        for(int j = 0; j < L; j++)
        {
            int cur = dp[i - 1][j];
            if(i < k)
                dp[i][j] = add(dp[i][j], mul(n - 1, cur));
            ans = add(ans, mul(j, mul(cur, cur_coeff)));
            if(i < k)
                dp[i][j - (j % i)] = add(dp[i][j - (j % i)], cur);
        }
        cur_coeff = divide(cur_coeff, n);
    }
    cout << ans << endl;        
}