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

int main()
{
    int n;
    while(cin>>n)
    {
        string s;
        cin>>s;
        int low=0,high=n-1,count=0;
        while(low<=high)
        {
            if(s[low]!=s[high])count++;
            low++;
            high--;
        }
        cout<<count<<endl;
    }
}

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, m;
    scanf("%d %d", &n, &m);
    if (n == 1 && m == 1) {
      printf("1\n");
      continue;
    }
    vector<int> fac_n, fac_m;
    for (int i = 2; i * i <= n; i++) {
      if (n % i == 0) {
        fac_n.pb(i);
        while (n % i == 0) n /= i;
      }
    }
    if (n > 1) fac_n.pb(n);
    for (int i = 2; i * i <= m; i++) {
      if (m % i == 0) {
        fac_m.pb(i);
        while (m % i == 0) m /= i;
      }
    }
    if (m > 1) fac_m.pb(m);
    sort(fac_n.begin(), fac_n.end());
    sort(fac_m.begin(), fac_m.end());
    int Min = 1e9;
    if (!fac_n.empty()) Min = min(Min, fac_n[0]);
    if (!fac_m.empty()) Min = min(Min, fac_m[0]);
    printf("%d\n", Min);
  }
  return 0;
}

int check(int mid) {
  for (int i = mid; i <= n; i++) {
    int res = 0;
    for (int j = 0; j < 30; j++) {
      if (sum[j][i] - sum[j][i - mid] > 0) {
        res |= (1 << j);
      }
    }
    if (res == Max) return true;
  }
  return false;
}
int main() {
  // cout << (1 << 30) << endl;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  Max = 0;
  for (int i = 1; i <= n; i++) {
    Max |= a[i];
  }
  for (int bit = 0; bit < 30; bit++) {
    sum[bit][0] = 0;
    for (int i = 1; i <= n; i++) {
      sum[bit][i] = sum[bit][i - 1];
      if (a[i] & (1 << bit)) {
        sum[bit][i]++;
      }
    }
  }
  int l = 1, r = n;
  while (abs(r - l) > 1) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  // cout << l << " " << r << endl;
  for (int i = min(l, r); i <= max(l, r); i++) {
    if (check(i)) {
      printf("%d\n", i);
      break;
    }
  }
  return 0;
}

void init() {
  for (int i = 0; i <= 1000; i++) c[i][0] = 1;
  for (int i = 0; i <= 1000; i++) c1[i][0] = 1;
  for (int i = 1; i <= 1000; i++) {
    for (int j = 1; j <= i; j++) {
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
      c1[i][j] = (c1[i - 1][j] + c1[i - 1][j - 1]);
    }
  }
}
struct Edge {
  int u, v, a, b;
};
int n, m;
vector<Edge> e;
int fa[1010];
int tfind(int x) {
  if (fa[x] == x)
    return x;
  else
    return fa[x] = tfind(fa[x]);
}
bool cmp(Edge &a, Edge &b) { return c1[a.a][a.b] > c1[b.a][b.b]; }
int main() {
  init();
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v, a, b;
    scanf("%d %d %d %d", &u, &v, &a, &b);
    e.push_back(Edge{u, v, a, b});
  }
  sort(e.begin(), e.end(), cmp);
  for (int i = 1; i <= n; i++) fa[i] = i;
  int num = 0;
  ll res = 0;
  for (const auto &it : e) {
    int u_root = tfind(it.u);
    int v_root = tfind(it.v);
    if (u_root == v_root) continue;
    res = (res + c[it.a][it.b]) % mod;
    num++;
    fa[u_root] = v_root;
    if (num == n - 1) break;
  }
  if (num != n - 1) {
    printf("-1\n");
  } else
    printf("%lld\n", res);
  return 0;
}