#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;
}