#include <bits/stdc++.h>
// jiangly
// https://codeforces.com/contest/1682/submission/158055817
// power 和 norm 和std有冲突
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
 
// 基于 mod P 的整数, structZ
constexpr int P = 1000000007;
// assume -P <= x < 2P
int mynorm(int x) {
  if (x < 0) {
    x += P;
  }
  if (x >= P) {
    x -= P;
  }
  return x;
}
template<class T>
T mypow(T a, ll b) {
  T res = 1;
  for (; b; b /= 2, a *= a) {
    if (b % 2) {
      res *= a;
    }
  }
  return res;
}
struct Z {
  int x;
  Z(int x = 0) : x(mynorm(x)) {}
  Z(ll x) : x(mynorm(x % P)) {}
  int val() const {
    return x;
  }
  Z operator-() const {
    return Z(mynorm(P - x));
  }
  Z inv() const {
    assert(x != 0);
    return mypow(*this, P - 2);
  }
  Z &operator*=(const Z &rhs) {
    x = ll(x) * rhs.x % P;
    return *this;
  }
  Z &operator+=(const Z &rhs) {
    x = mynorm(x + rhs.x);
    return *this;
  }
  Z &operator-=(const Z &rhs) {
    x = mynorm(x - rhs.x);
    return *this;
  }
  Z &operator/=(const Z &rhs) {
    return *this *= rhs.inv();
  }
  friend Z operator*(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res *= rhs;
    return res;
  }
  friend Z operator+(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res += rhs;
    return res;
  }
  friend Z operator-(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res -= rhs;
    return res;
  }
  friend Z operator/(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res /= rhs;
    return res;
  }
  friend istream &operator>>(istream &is, Z &a) {
    ll v;
    is >> v;
    a = Z(v);
    return is;
  }
  friend ostream &operator<<(ostream &os, const Z &a) {
    return os << a.val();
  }
};
 
// 树状数组 0-index
template <typename T>
struct Fenwick {
  const int n;
  vector<T> a;
  Fenwick(int n) : n(n){
    a.resize(n);
  }
  // [x] += v
  void add(int x, T v) {
    for (int i = x + 1; i <= n; i += i & -i) {
      a[i - 1] += v;
    }
  }
  // [0..x)
  T sum(int x) {
    T ans = 0;
    for (int i = x; i > 0; i -= i & -i) {
      ans += a[i - 1];
    }
    return ans;
  }
  // [l,r)
  T rangeSum(int l, int r) {
    return sum(r) - sum(l);
  }
};
 
int main() {
 
  int n = read(), q = read();
 
  vector<int> a(n);
  vector<ll> b(n + 1);
  rep(i,0,n) a[i] = read();
  // 倒序做差分
  per(i,1,n) a[i] -= a[i - 1];
  rep(i,1,n+1) {
    b[i] = read();
    // 前缀和
    b[i] += b[i - 1];
  }
  // 离线
  vector<array<ll, 4>> qry(q); // 查询 按照 {b[l-1],l-1,r,qidx} 排序
  rep(i,0,q) {
    int l = read()-1, r = read();
    qry[i] = {b[l], l, r, i};
  }
  sort(qry.begin(), qry.end());
 
  // https://en.cppreference.com/w/cpp/algorithm/ranges/iota
  // https://www.cplusplus.com/reference/numeric/iota/
  // 按照bi 前缀和 大小排序下标
  vector<int> p(n);
  iota(p.begin(), p.end(), 0);
  sort(p.begin(), p.end(), [&](int i, int j) { return b[i] < b[j]; });
 
  Fenwick<Z> s(n), c(n);
 
  rep(i,0,n) {
    // 先全部正贡献
    s.add(i, Z(b[i]) * a[i]);
    c.add(i, a[i]);
  }
  vector<Z> ans(q);
 
  int j = 0;
  for (auto [v, l, r, i] : qry) {
    while (j < n && b[p[j]] <= v) { // 根据 bi 前缀大小 决定贡献正负
      int k = p[j++];
      // 树状数组不支持修改, 只支持增量 ,实际是改成负贡献
      s.add(k, -2*Z(b[k]) * a[k]);
      c.add(k, -2*a[k]);
    }
 
    ans[i] = s.rangeSum(l, r) - c.rangeSum(l, r) * v;
  }
 
  for (auto x : ans) {
    printf("%d\n",x.val());
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb emplace_back
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
 
const int N = 200000;
 
int f[N+10]; // 前缀最大值[前缀左端点] = 最大右侧端点
ll a[N+10];
vector<int> gist[N+10]; // gist[值] = vector<int> 下标
pii seg[N+10]; // 题目给的线段
ll mnl[N+10]; // mnl[ir] = 最小合法il => [il..ir]没有重复的数
bool s[N+10]; // 存在过的数
int n,m;
 
void solve() {
  // clear
  fill(f,f+n,-1);
  fill(gist,gist+n,vector<int>());
 
  n = read();
  m = read();
  rep(i,0,n) a[i] = read();
  // 离散一下
  vector<pii> sa ;
  rep(i,0,n) sa.push_back({a[i],i});
  sort(all(sa));
  rep(i,0,n) {
    auto [v,j] = sa[i];
    if(i == 0) a[j] = 0;
    else if(v == sa[i-1].first) a[j] = a[sa[i-1].second];
    else a[j] = a[sa[i-1].second] + 1;
  }
 
  rep(i,0,n) gist[a[i]].pb(i);
 
  rep(i,0,m){
    int l = read();
    int r = read();
    seg[i] = {--l,--r};
    f[l] = max(f[l], r);
  }
  rep(i,1,n) f[i] = max(f[i-1],f[i]);
  // 双指针 [il...ir] 没有重复的数
  // mnl[ir] = 合法的最小il
  int il = n;
  per(ir,0,n){
    while (il && !s[a[il - 1]]) s[a[--il]] = true;
    mnl[ir] = il;
    s[a[ir]] = false;
  }
 
  // mnr 为L = 1 时 R的最小值 , [R+1..n] 要么就是 本身合法线段要么就是 [R+1..r] 合法
  ll mnr = -1;
  rep(i,0,m){
    auto [l,r] = seg[i];
    if (mnl[r] <= l) continue; // 本身就合法 直接忽略
    mnr = max(mnr, mnl[r] - 1);
  }
  if (mnr == -1) {
    printf("0\n");
    return;
  }
  ll ans = mnr + 1;
  // L 每次 +1
  // [l..mnr] => [l+1..?]
  rep(l,0,n-1){
    // l 不是 a[l] 首次出现的位置
    if (gist[a[l]][0] != l) {
      // 上一个同样值的位置
      int pr = *(--lower_bound(all(gist[a[l]]), l));
      // 左端点小于等于 pr, 的最大右端点, 如果删除了 就会有区间包含[pr...l] 有两个a[l]
      // 再移动 就不可能了, 所以直接break
      if (f[pr] >= l) break;
    }
    // 下一个 为a[l] 的 且在某个区间中
    if (gist[a[l]].back() > mnr ) {
      int nxt = *upper_bound(all(gist[a[l]]), mnr);
      if (f[l] >= nxt) mnr = nxt;
    }
    assert(mnr > l);
    ans = min(ans, mnr - l);
  }
  printf("%lld\n",ans);
}
 
int main() {
  int t = read();
  while (t--) solve();
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read
const int N = 1000;
vector<int> g[N+10]; // g[二分图左端点] = vector<>右端点
int with[N+10]; // with[右端点] = 链接的来源左端点
int vis[N+10]; // 二分图每轮选左侧起始点时,是否访问到
ll a[N+10];

bool dfs(int v) {
  if (vis[v]) return false;
  vis[v] = 1;
  // 直接就有可选终点
  for (auto to : g[v]) {
    if (with[to] == -1) {
      with[to] = v;
      return true;
    }
  }
  // 递归走 v -> to0 -> with[to0] -> t1 -> with[t1] - ... -> took
  for (auto to : g[v]) {
    if (dfs(with[to])) {
      with[to] = v; // 更新指向
      return true;
    }
  }
  return false;
}

int main() {
  int n = read();
  int A = read();
  // 二分图
  vector<ll> l;
  vector<ll> r;

  rep(i,0,n) {
    a[i] = read();
    (3 * a[i] > A ? l : r).pb(a[i]);
  }
  // 建立边
  rep(i,0,l.size()) {
    rep(j,0,r.size()) {
      if (l[i] % r[j])continue;
      if(2 * l[i] + r[j] > A) continue;
      g[i].pb(j);
    }
  }
  // 二分图匹配
  fill(with,with+r.size(),-1);
  rep(i,0,l.size()) {
    fill(vis,vis+l.size(),0);
    if(!dfs(i)){
      // 未消耗掉所有 > m/3
      printf("-1\n");
      return 0;
    }
  }
  vector<pair<ll,ll>> ans;
  rep(j,0,r.size()) {
    if (with[j] == -1) {
      ans.pb({3 * r[j], 2 * r[j]}); // <= m/3 的 直接 `3v,2v => v`
    } else { // 2v+i,v+i => v,i
      ans.pb({2 * l[with[j]] + r[j], l[with[j]] + r[j]});
    }
  }
  printf("%d\n",(int)ans.size());
  for (auto [a,b]: ans) printf("%lld %lld\n",a,b);
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)

// n(完全图), n-1, <= n-2?
int p2[1000010];

ll n ;
ll m ;
vector<int>uv;

void w(){
  scanf("%lld %lld",&n,&m);
  rep(i,0,m){
    int u,v;
    scanf("%d %d",&u,&v);
    p2[u] ++ ;
    p2[v] ++ ;
    uv.push_back(u);
    uv.push_back(v);
  }
  // 完全图
  if(m == n*(n-1)/2){
    printf("0\n");
    return ;
  }
  if(m == n*(n-1)/2 - 1){ 
    printf("-1\n");
    return ;
  }
  // 连了4个点 -2
  // 连了3个点 -1
  // sum n 很大
  if(n*(n-1)/2 - m > n){
    printf("-2\n");
    return ;
  }
    rep(i,1,n+1){
      if(p2[i] == n-1 - (n*(n-1)/2 - m)){
        printf("-1\n");
        return ;
      }
    }
  printf("-2\n");
}


int main(){
  int t;
  scanf("%d",&t);
  while(t--){
      w();
      for(auto u:uv)p2[u] = 0;
      uv = {};
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
const int N = 5e5;
int idx;
tuple<int,int,int> e[N*2 + 10]; // {u,v,d}
vector<pair<int,int> > u2vi[N+10]; // [u] = vector<{v,i}>
int loc[N*2+10]; // [d] = 深搜过程中 当前深搜链上 边为d的叶向端点
int lst[N*2+10]; // lst[v] = v作为叶节点父边为d , 通向根的链上,最近一个边为d的叶向节点 //上一个v'
int sz[N+10]; // 子树大小, 纯的树统计,不考虑边值
ll f[N*2+10]; // 考虑边值有效的树的大小
int n;
void dfs(int u, int fa) { // 点, 父节点
  sz[u] = 1; // 纯的子树大小
  for(auto [v,ei]: u2vi[u]){
    int d = get<2>(e[ei]);
    if (v == fa) continue;
    lst[v] = loc[d]; // 即帮助深搜恢复loc[d], 也自己记录了它到根的简单路径上最近的 边为d的叶向节点
    loc[d] = v; // 当前的深搜的链上 边为d的叶向端点
    dfs(v, u);
    loc[d] = lst[v]; // 恢复上一次的 loc[d]
    sz[u] += sz[v];
  }
  // 原理就很简单了 对于 u->v, 边为d 来说, 以v为根的连通块大小 = 它的子树大小 - sum{它子树中紧邻的边d的根为v' 的子树大小}
  f[u] += sz[u];
  f[lst[u]] -= sz[u];
}

int main() {
  cin >> n;
  rep(i,1,n){
    int u, v, d;
    scanf("%d %d %d",&u,&v,&d);
    e[i] = {u,v,d};
    u2vi[u].push_back({v,i});
    u2vi[v].push_back({u,i});
  }
  // 初始化f 和 loc
  rep(i,1,n+1){
    f[i + n] = n;
    loc[i] = i + n; // 初始化为每个值 对应虚拟节点为 value+n
  }
  dfs(1, -1);
  ll ans = 0;
  rep(i,2,n+1){
    ans += (f[i] * f[lst[i]]);
  }
  printf("%lld\n",ans);
  return 0;
}

rep(mask,0,1 << N){
  rep(i,0,1 << N){ // 枚举 mask, 检测是否是它的子集
    if((i&mask) == i) F[mask] += A[i];
  }
}

rep(mask,0,1 << N){
  F[mask] = A[0]; // 所有集合包含空集 空集合也作为停止条件
  for(int i = mask;i;i = (i-1)&mask){ // 这就是传说中的二进制枚举子集 ,
    F[mask] += A[i];
  }
}

rep(mask,0,1<<N) f[mask] = A[mask];
rep(i,0,N){
  // 这里不需要从大到小, 因为dp[mask]已经初始化了,只会更新1 << i上为1的,而更新的来源是1 << i上不是1的
  rep(mask,0,1 << N){
    if(mask & (1 << i)) f[mask]+=f[mask ^ (1 << i)];
  }
}

ans[mask] = 0;
sz = bitcount(mask)
rep(qmark,0,501){ // 自由的问号个数
  ti = pow(sz,qmark)
  for(int i = mask;i;i = (i-1)&mask){
    ans[mask] += cnt[i][qmark] * ti
  }
}

ans[mask] = 0;
sz = bitcount(mask)
for(int i = mask;i;i = (i-1)&mask){
  rep(qmark,0,501){
    ans[mask] += cnt[i][qmark] * pow(sz,qmark)
  }
}

rep(sz,1,17+1){
  cost[mask][sz] += pow(sz,qmark);
}

rep(sz,1,17+1){
  cost[mask][sz] += pow(sz,qmark) * pow(sz,total qmark - used qmark);
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

const int t = 17;
char s[1010]; // 读入
char s2[2010]; // 插入井号简化搜索
int n;

ll p[t+10][1010]; // 幂次预处理
ll cost[(1<<t)+10][t+10]; // 具体的值
ll ans[(1<<t)+10][t+10]; // 由具体值的子集和的答案
char query[t+10];

int main(){
  rep(i,1,t+1){
    p[i][0] = 1;
    rep(pwr,1,1000+1){
      p[i][pwr] = p[i][pwr-1]*i%MOD;
    }
  }
  scanf("%d",&n);
  scanf("%s",s);
  int qtotal = 0;
  rep(i,0,n) qtotal += s[i] == '?';
  // 字符两两间插入井号方便处理奇偶
  s2[0] = s[0];
  rep(i,1,n){
    s2[i*2-1] = '#';
    s2[i*2] = s[i];
  }
  // 中心
  rep(c,0,n*2-1){
    int mask = 0;
    int qmark = 0;
    int qcnt = 0;
    rep(l,0,n*2-1){ // 长度
      int il = c-l;
      int ir = c+l;
      if(il < 0 || ir >= n*2-1)break;
      qcnt += s2[il] == '?';
      qcnt += il != ir && s2[ir] == '?';
      if(s2[il] == '#')continue; // 不贡献的
      if(s2[il] == s2[ir]){
        if(s2[il] == '?'){
          qmark++;
        }
      }else{ // 不等
        if(s2[il] == '?'){
          mask |= (1 << (s2[ir] - 'a'));
        }else if(s2[ir] == '?'){
          mask |= (1 << (s2[il] - 'a'));
        }else{ // 不同的字符
          break;
        }
      }
      // 贡献统计
      rep(sz,1,17+1){
        // 不同字符串 同一个位置回文串的贡献要多次统计 所以要乘上 其余位置是问号的所有放入方案 让此处的贡献倍数 sz**(qtotal - qcnt)
        (cost[mask][sz] += p[sz][qmark] * p[sz][qtotal - qcnt] % MOD )%=MOD;
      }
    }
  }
  // sosdp
  rep(sz,1,t+1){
    rep(mask,0,1 << t){
      ans[mask][sz] = cost[mask][sz];
    }
    rep(i,0,t){
      rep(mask,0,1 << t){
        if(mask & (1 << i)) (ans[mask][sz] += ans[mask ^ (1 << i)][sz])%=MOD;
      }
    }
  }
  // query
  int q; // 2e5
  scanf("%d",&q);
  while(q--){
    // string to mask
    scanf("%s",query);
    int sz = strlen(query);
    int mask = 0;
    rep(i,0,sz){
      mask |= (1<<(query[i]-'a'));
    }
    printf("%lld\n", ans[mask][sz]);
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

namespace X{
  ll r(){ll r;scanf("%lld",&r);return r;} // read
  void add(ll &v0,ll &v1){(v0+=v1%MOD)%=MOD;} // add with MOD
};
using namespace X;

const int S = 10;

// mask 意义, mask中两两可换, 是X的最大前缀
// camp[mask0] = mask1, mask1任意一个bit 和 mask0 中的比它小的bit都没有链接
// 在 mask1中的digit 才能加入到 mask0
vector<int> camp(1<<S,(1<<S)-1);
bool conn[S][S]; // 连接状态
ll dp[2][1 << S];
int trans[1 << S][S]; // [mask][digit] = newmask,

int main() {
  int n = r();
  int m = r();
  rep(i,0,m) {
    int u = r();
    int v = r();
    conn[u][v] = conn[v][u] = 1;
  }
  // 计算 camp
  // O(S^2 * 2^S)
  rep(mask,0,1 << S){
    rep(c,0,S){ // c 在 mask 中
      if (!(mask & (1 << c))) continue;
      rep(j,c+1,S){ // j > c
        if (conn[c][j]) {
          camp[mask] &= ~(1 << j);
        }
      }
    }
  }
  // 计算trans
  // O(S^2 * 2^S)
  rep(mask,0,1 << S) {
    rep(c,0,S){
      trans[mask][c] = 1 << c;
      rep(j,0,S){
        // j 出现在mask 中, (c,j) 可以交换
        if ((mask & (1 << j)) && conn[c][j]) {// 和 mask 中存在相连
          trans[mask][c] |= 1 << j;
        }
      }
    }
  }
  // 滚动数组
  int cur = 0;
  dp[0][0] = 1;
  // O(n * S * 2^S)
  rep(i,0,n){
    // clear
    fill(dp[cur^1],dp[cur^1] + (1<<S),0);
    rep(mask,0,1<<S){
      if (dp[cur][mask] == 0) continue;
      rep(c,0,S){
        // 在camp[mask] 中的才能加
        if (!(camp[mask] & (1 << c))) continue;
        add(dp[cur ^ 1][trans[mask][c]] , dp[cur][mask]);
      }
    }
    cur ^= 1;
  }

  ll ans = 0;
  rep(mask,1,1<<S) add(ans,dp[cur][mask]);
  printf("%lld\n", ans);
}