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

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(const char *s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(const char *s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  for (int f = 0; L != R; L++)
    cerr << (f++ ? ", " : "") << *L;
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

struct Basis {
  vector<int> b;
  void insert(int x) {
    for (int y : b) x = min(x, x ^ y);
    if (x) b.push_back(x);
  }
  bool can_span(int x) {
    for (int y : b) x = min(x, x ^ y);
    return x == 0;
  }
};

const int mod = 998244353;
int modadd(int a, int b) {
  return a + b >= mod ? a + b - mod : a + b;
}
int modsub(int a, int b) {
  return a - b < 0 ? a - b + mod : a - b;
}
int modmul(int64_t a, int64_t b) {
  return static_cast<int>(a * b % mod);
}

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> cnt(n + 1), has(n + 1);
  vector<Basis> bas(n + 1);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    cnt[a[i]] += 1;
  }

  vector<int> pw(n + 1);
  pw[0] = 1;
  for (int i = 1; i <= n; i++)
    pw[i] = modadd(pw[i - 1], pw[i - 1]);

  int ans = 0;

  int all_has = 0;
  Basis all_b;
  for (int i = 1; i <= n; i++) {
    all_has += cnt[i];
    if (cnt[i])
      all_b.insert(i);
  }

  {
    int k = all_has - int(all_b.b.size());
    ans = modadd(ans, modsub(pw[k], 1));
    debug(k, pw[k]);
  }

  for (int i = 1; i <= n; i++) {
    if (cnt[i]) {
      for (int j = i * 2; j <= n; j += i) {
        has[j] += cnt[i];
        bas[j].insert(i);
      }

      if (cnt[i] == 1) {
        int k = has[i] - int(bas[i].b.size());
        ans = modadd(ans, pw[k]);
      } else {
        int k = has[i] - int(bas[i].b.size());
        ans = modadd(ans, modmul(pw[k], pw[cnt[i] - 1]));
        if (bas[i].can_span(i))
          ans = modadd(ans, modmul(pw[k], modsub(pw[cnt[i] - 1], 1)));
      }
    }
  }

  cout << ans << '\n';
}

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

  return 0;
}