#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,t,tt;
 
int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
	    printf("? 1\n");
	    fflush(stdout);
	    scanf("%d",&t);
	    printf("? %d\n",t*2);
	    fflush(stdout);
	    scanf("%d",&tt);
	    printf("! %d\n",t*2-(tt!=t*2));
	    fflush(stdout);
	}
	
	//fclose(stdin);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
       ll n,m,x,y,k;
       cin>>n>>m>>x>>y>>k;
       ll a1=(n*m)-(n*y);
       ll a2=(n*m)-(m*x);
       ll a3=(n*m)-(n*(m-y+1));
       ll a4=(n*m)-(m*(n-x+1));
       if(k==0) cout<<0<<endl;
       else if(k==1) cout<<max({a1,a2,a3,a4})<<endl;
       else if(k==2){
           ll b1=a1+max((n-x)*y,(x-1)*y);
           ll b2=a2+max(x*(y-1),x*(m-y));
           ll b3=a3+max((m-y+1)*(x-1),(m-y+1)*(n-x));
           ll b4=a4+max((n-x+1)*(m-y),(n-x+1)*(y-1));
           ll b5=a1+a3;
           ll b6=a2+a4;
           cout<<max({b1,b2,b3,b4,b5,b6})<<endl;
       }
       else if(k==3){
           a1=n-x;
           a2=x-1;
           a3=m-y;
           a4=y-1;
           cout<<n*m-1-min({a1,a2,a3,a4})<<endl;
       }
       else cout<<(n*m-1)<<endl;
    }
}

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
 
using namespace std;
 
int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
 
        int t;
        cin >> t;
 
        while (t --> 0) {
                int n;
                cin >> n;
 
                map<int, int> cnt;
                vector<pair<int, int>> a;
                for (int i = 1; i <= n; i++) {
                        int x;
                        cin >> x;
 
                        cnt[x] += 1;
                        a.push_back({x, i});
                }
                sort(a.begin(), a.end(), [&](pair<int, int> x, pair<int, int> y) {
                        if (x.fi != y.fi) return x.fi < y.fi;
                        return x.se > y.se;
                });
 
                vector<int> fen(n + 1);
 
                auto upd = [&](int x, int val) {
                        for (; x <= n; x += x & -x) fen[x] += val;
                };
 
                auto get = [&](int x) {
                        int res = 0;
                        for (; x > 0; x -= x & -x) res += fen[x];
                        return res;
                };
 
                for (int i = 1; i <= n; i++) upd(i, 1);
 
                int lst = 0, cur = 0;
                vector<int> ans(n + 1);
                for (int p = 0; p < n; p++) {
                        auto [x, i] = a[p];
                        if (p == 0) {
                                cur += (x - 1) * n;
                                lst = x - 1;
                        } else if (a[p - 1].fi != x) {
                                cur += (x - lst - 1) * get(n);
                                cur += cnt[lst + 1];
                                lst = x - 1;
                        }
                        
                        ans[i] = cur + get(i);
                        upd(i, -1);
                }
 
                for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
        }
        
        return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        --u; --v; --c;
        g[u].push_back({v, c});
    }
    vector<int> ans(n);
    vector<vector<int>> colors(n);
    colors[0].push_back(-1);
    colors[0].push_back(-1);
    vector<int> Q;
    Q.push_back(0);
    while (!Q.empty()) {
        int u = Q.back();
        Q.pop_back();
        ans[u] = true;
        if (colors[u].size() == 2) {
            for (auto el : g[u]) {
                int v = el.first;
                int c = el.second;
                if (colors[v].size() == 2) {
                    continue;
                }
                if (colors[v].empty()) {
                    colors[v].push_back(c);
                    Q.push_back(v);
                    continue;
                }
                if (colors[v][0] != c) {
                    colors[v].push_back(c);
                    Q.push_back(v);
                }
            }
        } else if (colors[u].size() == 1) {
            int cur = colors[u][0];
            for (auto el : g[u]) {
                int v = el.first;
                int c = el.second;
                if (c == cur) {
                    continue;
                }
                if (colors[v].size() == 2) {
                    continue;
                }
                if (colors[v].empty()) {
                    colors[v].push_back(c);
                    Q.push_back(v);
                    continue;
                }
                if (colors[v][0] != c) {
                    colors[v].push_back(c);
                    Q.push_back(v);
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (ans[i]) {
            cout << i + 1 << " ";
        }
    }
    cout << "\n";
}
 
int32_t main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        solve();
    }
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
using pi=pair<int,int>;
 
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &nx : a){cin >> nx;}
    vector<int> b(n);
    for(auto &nx : b){cin >> nx;}
    vector<int> c(n);
    for(auto &nx : c){cin >> nx;}
 
    // 0 ... nothing
    // 1 ... cc...caa...acc...
    // 2 ... cc...caa...a
    vector<vector<long long>> dp(n,vector<long long>(3,-8e18));
    vector<vector<pi>> pre(n,vector<pi>(3));
 
    dp[0][0]=b[0];
    pre[0][0]={-1,1};
    dp[0][1]=c[0];
    pre[0][1]={-1,2};
    for(int i=1;i<n;i++){
      // from 0
      if(dp[i][0] < dp[i-1][0]+b[i]){
        dp[i][0]=dp[i-1][0]+b[i];
        pre[i][0]={0,1};
      }
      if(dp[i][1] < dp[i-1][0]+c[i]){
        dp[i][1]=dp[i-1][0]+c[i];
        pre[i][1]={0,2};
      }
 
      // from 1
      if(dp[i][2] < dp[i-1][1]+a[i]){
        dp[i][2]=dp[i-1][1]+a[i];
        pre[i][2]={1,0};
      }
      if(dp[i][1] < dp[i-1][1]+b[i]){
        dp[i][1]=dp[i-1][1]+b[i];
        pre[i][1]={1,1};
      }
      if(dp[i][1] < dp[i-1][1]+c[i]){
        dp[i][1]=dp[i-1][1]+c[i];
        pre[i][1]={1,2};
      }
 
      // from 2
      if(dp[i][2] < dp[i-1][2]+a[i]){
        dp[i][2]=dp[i-1][2]+a[i];
        pre[i][2]={2,0};
      }
      if(dp[i][2] < dp[i-1][2]+b[i]){
        dp[i][2]=dp[i-1][2]+b[i];
        pre[i][2]={2,1};
      }
      if(dp[i][1] < dp[i-1][2]+c[i]){
        dp[i][1]=dp[i-1][2]+c[i];
        pre[i][1]={2,2};
      }
    }
 
    // for(auto &nx : dp){
    //   for(auto &ny : nx){cout << ny << " ";}
    //   cout << "\n";
    // }
 
    vector<int> pt;
    int tg;
    if(dp[n-1][0]<dp[n-1][2]){tg=2;}else{tg=0;}
 
    // cout << max(dp[n-1][0],dp[n-1][2]) << "\n";
 
    vector<int> his(n);
    for(int i=n-1;i>=0;i--){
      his[i]=pre[i][tg].second;
      tg=pre[i][tg].first;
    }
 
    vector<int> p(n);
    int ofs=0;
    vector<int> sft;
 
    // for(auto &nx : his){cout << nx << " ";}cout << "\n";
 
    his.push_back(2);
    int phs=0;
 
    for(int i=0;i<=n;i++){
      if(his[i]==2){
        if(phs==2){
          int sz=sft.size();
          for(int i=0;i<sz;i++){
            p[sft[(i+ofs)%sz]]=sft[i];
          }
          ofs=0;
          sft.clear();
        }
 
        sft.push_back(i);
        ofs++;
        phs=1;
      }
      else if(his[i]==1){p[i]=i;}
      else if(his[i]==0){
        if(phs==1){phs=2;}
        sft.push_back(i);
      }
    }
 
    long long act=0;
    for(int i=0;i<n;i++){
      if(p[i]<i){act+=a[i];}
      else if(p[i]==i){act+=b[i];}
      else{act+=c[i];}
    }
    // cout << act << "\n";
 
    for(int i=0;i<n;i++){
      if(i){cout << " ";}
      cout << p[i]+1;
    }cout << "\n";
  }
  return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const long double PI=acosl(-1);
const int MAXN=2e5+2;
pair<long double,long double> xy[MAXN];
vector<pair<long double,bool>> sweep;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n,m;
        cin >> n >> m;
        long double x,y,ang,rot=2*PI/m,maxDist=0;
        for (int i=1;i<=n;i++) {
            cin >> x >> y;
            ang=atan2l(y,x);
            ang-=floorl(ang/rot)*rot;
            xy[i]={sqrtl(x*x+y*y),ang};
            maxDist=max(maxDist,xy[i].first);
        }
        long double l=maxDist,r=3*maxDist,mid;
        int cnt,cnt2;
        while (r-l >= 1e-10) {
            cnt=0;cnt2=0;sweep.clear();
            mid=(l+r)/2; // bin search on size
            for (int i=1;i<=n;i++) {
                if (xy[i].first <= mid*cosl(rot/2)) continue;
                cnt++;
                ang=rot/2-acosl(mid*cosl(rot/2)/xy[i].first);
                if (xy[i].second < ang) {
                    sweep.push_back({rot+xy[i].second-ang,0});
                    sweep.push_back({ang+xy[i].second,1});
                    sweep.push_back({0,0});
                }
                else if (xy[i].second >= rot-ang) {
                    sweep.push_back({0,0});
                    sweep.push_back({ang-rot+xy[i].second,1});
                    sweep.push_back({xy[i].second-ang,0});
                }
                else {
                    sweep.push_back({ang+xy[i].second,1});
                    sweep.push_back({xy[i].second-ang,0});
                }
            }
            sort(sweep.begin(),sweep.end());
            for (auto &i : sweep) {
                if (i.second) cnt2--;
                else cnt2++;
                if (cnt2 == cnt) break;
            }
            if (cnt2 != cnt) l=mid;
            else r=mid;
        }
        cout << setprecision(10) << l << endl;
    }
}

#include<bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    long long n;
    cin >> n;
    deque<long long> dq;
    for(long long i=0;i<n;i++){
      long long x;
      cin >> x;
      dq.push_back(x);
    }
    long long res=0;
    while(dq.size()>=2){
      long long pre=dq.front();dq.pop_front();
      long long bac=dq.back();dq.pop_back();
      if(pre==bac){continue;}
      if(pre<bac){
        res++;
        dq.push_back(bac-pre);
      }
      else{
        res++;
        dq.push_front(pre-bac);
      }
    }
    cout << res << "\n";
  }
  return 0;
}

#include<bits/stdc++.h>

using namespace std;
using pl=pair<long long,long long>;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    long long n,m;
    cin >> n >> m;
    vector<long long> a(n);
    for(auto &nx : a){cin >> nx;}
    vector<long long> b(n);
    for(auto &nx : b){cin >> nx;}

    vector<long long> eff;
    for(long long i=0;i<n;i++){
      m+=a[i];
      eff.push_back(a[i]+b[i]);
    }
    sort(eff.begin(),eff.end());
    reverse(eff.begin(),eff.end());
    long long res=-1;
    for(long long i=0;i<n;i++){
      m-=eff[i];
      if(m<=0){res=i+1;break;}
    }
    cout << res << "\n";
  }
  return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  std::random_device seed_gen;
  std::mt19937_64 engine(seed_gen());

  int k;
  cin >> k;
  vector<string> s(20);
  vector<vector<int>> bk(20,vector<int>(10,0));

  for(int i=0;i<20;i++){
    cin >> s[i];
    for(int j=0;j<k;j++){
      bk[i][s[i][j]-'0']++;
    }
  }

  vector<pair<int,int>> vp;
  for(int i=0;i<20;i++){
    for(int j=i+1;j<20;j++){
      vp.push_back({i,j});
    }
  }
  shuffle(vp.begin(),vp.end(),engine);

  vector<int> p={0,1,2,3,4,5,6,7,8,9};

  for(auto &nx : vp){
    int i=nx.first;
    int j=nx.second;
    shuffle(p.begin(),p.end(),engine);
    for(auto &tg : p){
      if(min(bk[i][tg],bk[j][tg])>=(k/10)){
        string res;

        int p=0,q=0;
        while(p<k && q<k){
          if(s[i][p]-'0' != tg){
            res.push_back(s[i][p]);
            p++;
            continue;
          }
          if(s[j][q]-'0' != tg){
            res.push_back(s[j][q]);
            q++;
            continue;
          }
          res.push_back(s[i][p]);
          p++;q++;
        }

        while(p<k){res.push_back(s[i][p]);p++;}
        while(q<k){res.push_back(s[j][q]);q++;}

        while(res.size()<(k/10)*19){
          res.push_back('0'+(engine()%10));
        }
        cout << res << "\n";
        return 0;
      }
    }
  }
  return 0;
}

// factorize
// https://judge.yosupo.jp/problem/factorize
#include<bits/stdc++.h>

using namespace std;

// https://hitonanode.github.io/cplib-cpp/number/binary_gcd.hpp.html
template <typename Int> Int binary_gcd(Int x_, Int y_) {
  unsigned long long x = x_ < 0 ? -x_ : x_, y = y_ < 0 ? -y_ : y_;
  if (!x or !y) return x + y;
  int n = __builtin_ctzll(x), m = __builtin_ctzll(y);
  x >>= n, y >>= m;
  while (x != y) {
    if (x > y) {
      x = (x - y) >> __builtin_ctzll(x - y);
    } else {
      y = (y - x) >> __builtin_ctzll(y - x);
    }
  }
  return x << (n > m ? m : n);
}

struct factorizer{
  long long smlrng;
  vector<long long> lpf;
  vector<long long> plis;
  // init
  // https://37zigen.com/linear-sieve/
  factorizer(long long smlrng_){
    smlrng = smlrng_;
    lpf.resize(smlrng+1);
    fill(lpf.begin(),lpf.end(),0);
    plis.clear();
    for(long long i=2;i<=smlrng;i++){
      if(lpf[i]==0){
        lpf[i]=i;
        plis.push_back(i);
      }
      for(auto &p : plis){
        if(p*i > smlrng || p>lpf[i]){break;}
        lpf[p*i]=p;
      }
    }
  }

  vector<long long> tinyplis = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

  long long mulmn(long long a,long long b,long long n){
    __int128 c128=a;
    c128*=b;
    return ((long long)(c128%n));
  }
  long long powmn(long long a,long long b,long long n){
    long long res=1;
    while(b>0){
      if(b&1ll){
        res=mulmn(res,a,n);
      }
      a=mulmn(a,a,n);
      b/=2;
    }
    return res;
  }

  bool isprime(long long n){
    if(n<=1){return false;}
    if(n<=smlrng){return (n==lpf[n]);}
    for(auto &p : tinyplis){
      if(n%p==0){return false;}
    }

    // from now, n should be odd
    // https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
    vector<long long> a={2,7,61};
    if(n>=(1ll<<32)){
      a = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    }

    long long s=__builtin_ctzll(n-1);
    long long d=((n-1)>>s);
    for(auto &ca : a){
      if(powmn(ca,d,n)==1){continue;}
      bool cp=true;
      for(long long r=0;r<s;r++){
        if(powmn(ca,(1ll<<r)*d,n)==(n-1)){cp=false;break;}
      }
      if(cp){return false;}
    }
    return true;
  }

  long long ffrho(long long n){
    long long m=(1ll<<((64-__builtin_clzll(n))/8));
    for(long long c=1;;c++){
      auto f = [&](long long v){ return (mulmn(v,v,n)+c)%n; } ;
      long long x,y=2,r=1,q=1,g=1,ys;
      while(g==1){
        x=y;
        for(long long i=0;i<r;i++){
          y=f(y);
        }
        long long k=0;
        while(k<r && g==1){
          ys=y;
          for(long long i=0;i<min(m,r-k);i++){
            y=f(y);
            q=mulmn(q,abs(x-y),n);
          }
          g=binary_gcd(q,n);
          k+=m;
        }
        r<<=1;
      }
      if(g==n){
        g=1;
        while(g==1){
          ys=f(ys);
          g=binary_gcd(abs(x-ys),n);
        }
      }
      if(g<n){
        if(isprime(g)){return g;}
        else if(isprime(n/g)){return (n/g);}
        return ffrho(g);
      }
    }
  }

  // https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
  vector<long long> factorize(long long n){
    vector<long long> res;
    for(auto &p : tinyplis){
      while(n%p==0){
        n/=p;
        res.push_back(p);
      }
    }
    while(n>1){
      if(isprime(n)){res.push_back(n);break;}
      long long cf=ffrho(n);
      while(n%cf==0){
        n/=cf;
        res.push_back(cf);
      }
    }
    sort(res.begin(),res.end());
    return res;
  }
};

vector<int> gb(int x,factorizer &fz){
  for(int i=2;i<=x-i;i++){
    if(fz.isprime(i) && fz.isprime(x-i)){
      return {i,x-i};
    }
  }
  return {-1,-1};
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  factorizer fz(10000005);
  int t;
  cin >> t;
  while(t>0){
    t--;
    int x,y;
    cin >> x >> y;
    if(fz.isprime(x+y)){
      cout << 1 << "\n";
      cout << x << " " << y << "\n";
      continue;
    }
    else if(fz.isprime(x+y-2)){
      cout << 2 << "\n";
      cout << 1 << " " << 1 << "\n";
      cout << x << " " << y << "\n";
      continue;
    }
    else if((x+y)%2==0){
      vector<int> v=gb(x+y,fz);

      cout << v.size() << "\n";
      int s=0;
      for(auto &nx : v){
        s+=nx;
        cout << min(x,s) << " " << max(0,s-x) << "\n";
      }
    }
    else{
      vector<int> v=gb(x+y-3,fz);
      v.push_back(3);

      cout << v.size() << "\n";
      int s=0;
      for(auto &nx : v){
        s+=nx;
        cout << min(x,s) << " " << max(0,s-x) << "\n";
      }
    }
  }
  return 0;
}

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    int n,k;
    cin >> n >> k;
    vector<int> inv(n);
    for(int i=0;i<n;i++){
      int p;
      cin >> p;
      p--;
      inv[p]=i;
    }

    set<pi> st;
    for(int i=0;i<k+5;i++){
      st.insert({-1,1e9+i});
      st.insert({n,1e9+i});
    }

    vector<int> res(n,0);

    for(int i=n-1;i>=0;i--){
      auto ifw=st.lower_bound({inv[i],i});
      auto ibk=ifw;ibk--;
      vector<int> pf,pb;
      for(int i=0;i<k;i++){
        pf.push_back((*ifw).first);ifw++;
        pb.push_back((*ibk).first);ibk--;
      }
      // for(auto &nx : pf){cout << nx << " ";}cout << "\n";
      // for(auto &nx : pb){cout << nx << " ";}cout << "\n";
      for(int p=0;p<k;p++){
        int q=k-1-p;
        res[inv[i]]=max(res[inv[i]],pf[p]-pb[q]-1);
      }
      st.insert({inv[i],i});
    }

    for(int i=0;i<n;i++){
      if(i){cout << " ";}
      cout << res[i];
    }cout << "\n";
  }
  return 0;
}

#include<bits/stdc++.h>

#include <algorithm>

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder

#include <cassert>
#include <vector>

namespace atcoder {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder

using namespace std;
using namespace atcoder;

long long big=2e9;
long long op(long long a,long long b){
  return min(a*b,big);
}
long long e(){
  return 1;
}

long long power(long long a,long long b){
  long long res=e();
  while(b>0){
    if(b&1ll){
      res=op(res,a);
    }
    a=op(a,a);
    b/=2;
  }
  return res;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    long long n,k;
    cin >> n >> k;

    long long gtn=0;
    vector<long long> bk(n+1,0);
    for(long long i=0;i<n;i++){
      long long a;
      cin >> a;
      if(a>n){gtn++;}
      else{bk[a]++;}
    }

    vector<long long> ini(n+2);
    for(long long i=0;i<=n;i++){
      ini[i]=power(2,bk[i]);
    }
    ini[n+1]=power(2,gtn);

    segtree<long long,op,e> seg(ini);
    vector<long long> cnt(n+1);
    for(long long i=0;i<=n;i++){
      seg.set(i,1); // not contain
      cnt[i]=seg.all_prod();
      seg.set(i,power(2,bk[i])-1); // at least 1
    }
    cnt[0]--; // remove empty set

    long long pre=(k+1)/2;
    long long suf=k-pre;
    long long res=0;
    for(long long i=0;i<=n;i++){
      long long del=min(pre,cnt[i]);
      pre-=del;
      res+=del*i;
    }
    for(long long i=n;i>=0;i--){
      long long del=min(suf,cnt[i]);
      suf-=del;
      res-=del*i;
    }
    // for(auto &nx : cnt){
    //   cout << nx << " ";
    // }cout << "\n";
    cout << res << "\n";
  }
  return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;

    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    int fw=(k+1)/2;
    int bc=k/2;
    int md=n-fw-bc;

    string pre,mid,suf;

    for(char c='a';c<='z';c++){
      for(int i=n-1;i>=0;i--){
        if(pre.size()<fw && s[i]==c){
          pre.push_back(s[i]);
          s[i]='*';
        }
      }
    }

    string ns;
    for(auto &nx : s){
      if(nx!='*'){ns.push_back(nx);}
    }

    int l=ns.size();
    vector<vector<int>> mem(l+1);
    vector<int> bk(26,1e9);
    mem[l]=bk;
    for(int i=l-1;i>=0;i--){
      bk[ns[i]-'a']=i;
      mem[i]=bk;
    }

    int pt=0;
    while(mid.size()<md){
      // cerr << mid << " " << pt << "\n";
      for(int i=0;i<26;i++){
        // cerr << pt << " " << i << " " << ((int)mid.size())+(l-mem[pt][i]) << "\n";
        if(((int)mid.size())+(l-mem[pt][i]) >= md){
          mid.push_back(ns[mem[pt][i]]);
          ns[mem[pt][i]]='*';
          pt=mem[pt][i]+1;
          break;
        }
      }
    }

    for(auto &nx : ns){
      if(nx!='*'){
        suf.push_back(nx);
      }
    }
    sort(suf.begin(),suf.end());
    cout << pre+mid+suf << "\n";
  }
  return 0;
}