#include <bits/stdc++.h>
using namespace std;
using VS = vector<string>;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using VL = vector<LL>;
using VVL = vector<VL>;
const int INF = 1e9;
const LL LINF = 1e16;
const LL MOD = 998244353;
const double PI = acos(-1.0);
int DX[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int DY[8] = {1, -1, 0, 0, 1, -1, 1, -1};
LL read() {
  LL in;
  scanf("%lld", &in);
  return in;
}
std::vector<int> isBipartiteGraph(const std::vector<std::vector<int>> &g) {
  int n = g.size();
  std::vector<int> color(n, -1);
  std::queue<int> que;
  que.push(0);
  color[0] = 0;
  while (!que.empty()) {
    int now = que.front();
    que.pop();
    for (auto to : g[now]) {
      if (color[to] != -1) {
        if (color[now] == color[to]) {
          return std::vector<int>();
        }
      } else {
        color[to] = color[now] ^ 1;
        que.push(to);
      }
    }
  }
  return color;
}
template <::std::uint_fast32_t MODULO>
class modint {
 public:
  using uint32 = ::std::uint_fast32_t;
  using uint64 = ::std::uint_fast64_t;
  using value_type = uint32;
  uint32 a;
  modint() noexcept : a(0) {}
  modint(const uint32 x) noexcept : a(x) {}
  modint operator+(const modint &o) const noexcept {
    return a + o.a < MODULO ? modint(a + o.a) : modint(a + o.a - MODULO);
  }
  modint operator-(const modint &o) const noexcept {
    return modint(a < o.a ? a + MODULO - o.a : a - o.a);
  }
  modint operator*(const modint &o) const noexcept {
    return modint(static_cast<uint64>(a) * o.a % MODULO);
  }
  modint operator/(const modint &o) const {
    return modint(static_cast<uint64>(a) * (~o).a % MODULO);
  }
  modint &operator+=(const modint &o) noexcept { return *this = *this + o; }
  modint &operator-=(const modint &o) noexcept { return *this = *this - o; }
  modint &operator*=(const modint &o) noexcept { return *this = *this * o; }
  modint &operator/=(const modint &o) { return *this = *this / o; }
  modint operator~() const noexcept { return pow(MODULO - 2); }
  modint operator-() const noexcept { return a ? modint(MODULO - a) : *this; }
  modint operator++() noexcept { return a == MODULO - 1 ? a = 0 : ++a, *this; }
  modint operator--() noexcept { return a ? --a : a = MODULO - 1, *this; }
  bool operator==(const modint &o) const noexcept { return a == o.a; }
  bool operator!=(const modint &o) const noexcept { return a != o.a; }
  bool operator<(const modint &o) const noexcept { return a < o.a; }
  bool operator<=(const modint &o) const noexcept { return a <= o.a; }
  bool operator>(const modint &o) const noexcept { return a > o.a; }
  bool operator>=(const modint &o) const noexcept { return a >= o.a; }
  explicit operator bool() const noexcept { return a; }
  explicit operator uint32() const noexcept { return a; }
  modint pow(uint32 x) const noexcept {
    uint64 t = a, u = 1;
    while (x) {
      if (x & 1) u = u * t % MODULO;
      t = (t * t) % MODULO;
      x >>= 1;
    }
    return modint(u);
  }
  uint32 get() const noexcept { return a; }
};
using mint = modint<MOD>;
class SCC {
 private:
  const int n;
  vector<vector<int>> G;
  vector<vector<int>> rG;
  vector<int> vs;
  vector<bool> used;
  vector<int> cmp;
  int sccsize_k;

 public:
  SCC(int _n) : n(_n), G(_n), rG(_n), used(_n), cmp(_n) {}
  void addEdge(int from, int to) {
    G[from].emplace_back(to);
    rG[to].emplace_back(from);
  }
  void dfs(int v) {
    used[v] = true;
    for (auto &&nxt : G[v]) {
      if (!used[nxt]) dfs(nxt);
    }
    vs.emplace_back(v);
  }
  void rdfs(int v, int k) {
    used[v] = true;
    cmp[v] = k;
    for (auto &&nxt : rG[v]) {
      if (!used[nxt]) rdfs(nxt, k);
    }
    vs.emplace_back(v);
  }
  int scc() {
    for (int v = 0; v < n; v++) {
      if (!used[v]) dfs(v);
    }
    used.assign(n, false);
    sccsize_k = 0;
    for (int i = vs.size() - 1; i >= 0; i--) {
      int v = vs[i];
      if (!used[v]) rdfs(v, sccsize_k++);
    }
    return sccsize_k;
  }
  bool same(int a, int b) { return cmp[a] == cmp[b]; }
  vector<int> get_color() { return cmp; }
};
vector<VVI> ForestToGraphs(vector<PII> &edge, int V) {
  SCC SccG(V);
  for (const auto &it : edge) {
    SccG.addEdge(it.first, it.second);
    SccG.addEdge(it.second, it.first);
  }
  int scc_sz = SccG.scc();
  VI color = SccG.get_color();
  vector<VVI> ret(scc_sz);
  map<PII, int> Map;
  map<int, int> CC;
  auto reid = [&Map, &CC](int c, int x) {
    if (Map.find(PII(c, x)) == Map.end()) {
      int nc = CC[c];
      Map[PII(c, x)] = nc;
      CC[c]++;
    }
    return Map[PII(c, x)];
  };
  vector<vector<PII>> edges(scc_sz);
  for (int(i) = (0); (i) < (int((edge).size())); (i)++) {
    int a, b;
    tie(a, b) = edge[i];
    int c = color[a];
    a = reid(c, a), b = reid(c, b);
    edges[c].push_back(PII(a, b));
  }
  for (int(i) = (0); (i) < (scc_sz); (i)++) {
    ret[i].resize(CC[i]);
    for (int(j) = (0); (j) < (int((edges[i]).size())); (j)++) {
      int a, b;
      tie(a, b) = edges[i][j];
      ret[i][a].push_back(b);
      ret[i][b].push_back(a);
    }
  }
  return ret;
}
int main() {
  int T = read();
  for (int(_) = (0); (_) < (T); (_)++) {
    LL N = read(), M = read();
    SCC SG(N);
    vector<PII> edge(M);
    for (int(i) = (0); (i) < (M); (i)++) {
      int a = read() - 1, b = read() - 1;
      edge[i] = PII(a, b);
    }
    vector<VVI> forest = ForestToGraphs(edge, N);
    int f = 1;
    mint ans = 1;
    for (int(j) = (0); (j) < (int((forest).size())); (j)++) {
      ;
      if (int((forest[j]).size()) == 0) {
        ans *= 3;
        ;
        continue;
      }
      VI res = isBipartiteGraph(forest[j]);
      if (int((res).size())) {
        int B = 0;
        for (int(i) = (0); (i) < (int((forest[j]).size())); (i)++) {
          if (res[i] == 1) {
            B++;
          }
        }
        int R = int((forest[j]).size()) - B;
        mint two = 2;
        mint ret = 0;
        ret += two.pow(R);
        ret += two.pow(B);
        ans *= ret;
      } else {
        f = 0;
      };
    }
    if (f) {
      cout << ans.get() << endl;
    } else {
      cout << 0 << endl;
    }
  }
  return 0;
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

You are given an undirected unweighted graph consisting of n vertices and m edges.

You have to write a number on each vertex of the graph. Each number should be 1, 2 or 3. The graph becomes beautiful if for each edge the sum of numbers on vertices connected by this edge is odd.

Calculate the number of possible ways to write numbers 1, 2 and 3 on vertices so the graph becomes beautiful. Since this number may be large, print it modulo 998244353.

Note that you have to write exactly one number on each vertex.

The graph does not have any self-loops or multiple edges.

Input

The first line contains one integer t (1 ≤ t ≤ 3 ⋅ 10^5) — the number of tests in the input.

The first line of each test contains two integers n and m (1 ≤ n ≤ 3 ⋅ 10^5, 0 ≤ m ≤ 3 ⋅ 10^5) — the number of vertices and the number of edges, respectively. Next m lines describe edges: i-th line contains two integers u_i,  v_i (1 ≤ u_i, v_i ≤ n; u_i ≠ v_i) — indices of vertices connected by i-th edge.

It is guaranteed that ∑_{i=1}^{t} n ≤ 3 ⋅ 10^5 and ∑_{i=1}^{t} m ≤ 3 ⋅ 10^5.

Output

For each test print one line, containing one integer — the number of possible ways to write numbers 1, 2, 3 on the vertices of given graph so it becomes beautiful. Since answers may be large, print them modulo 998244353.

Example

Input


2
2 1
1 2
4 6
1 2
1 3
1 4
2 3
2 4
3 4


Output


4
0

Note

Possible ways to distribute numbers in the first test: 

  1. the vertex 1 should contain 1, and 2 should contain 2; 
  2. the vertex 1 should contain 3, and 2 should contain 2; 
  3. the vertex 1 should contain 2, and 2 should contain 1; 
  4. the vertex 1 should contain 2, and 2 should contain 3. 



In the second test there is no way to distribute numbers.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using VS = vector<string>;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using VL = vector<LL>;
using VVL = vector<VL>;
const int INF = 1e9;
const LL LINF = 1e16;
const LL MOD = 998244353;
const double PI = acos(-1.0);
int DX[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int DY[8] = {1, -1, 0, 0, 1, -1, 1, -1};
LL read() {
  LL in;
  scanf("%lld", &in);
  return in;
}
std::vector<int> isBipartiteGraph(const std::vector<std::vector<int>> &g) {
  int n = g.size();
  std::vector<int> color(n, -1);
  std::queue<int> que;
  que.push(0);
  color[0] = 0;
  while (!que.empty()) {
    int now = que.front();
    que.pop();
    for (auto to : g[now]) {
      if (color[to] != -1) {
        if (color[now] == color[to]) {
          return std::vector<int>();
        }
      } else {
        color[to] = color[now] ^ 1;
        que.push(to);
      }
    }
  }
  return color;
}
template <::std::uint_fast32_t MODULO>
class modint {
 public:
  using uint32 = ::std::uint_fast32_t;
  using uint64 = ::std::uint_fast64_t;
  using value_type = uint32;
  uint32 a;
  modint() noexcept : a(0) {}
  modint(const uint32 x) noexcept : a(x) {}
  modint operator+(const modint &o) const noexcept {
    return a + o.a < MODULO ? modint(a + o.a) : modint(a + o.a - MODULO);
  }
  modint operator-(const modint &o) const noexcept {
    return modint(a < o.a ? a + MODULO - o.a : a - o.a);
  }
  modint operator*(const modint &o) const noexcept {
    return modint(static_cast<uint64>(a) * o.a % MODULO);
  }
  modint operator/(const modint &o) const {
    return modint(static_cast<uint64>(a) * (~o).a % MODULO);
  }
  modint &operator+=(const modint &o) noexcept { return *this = *this + o; }
  modint &operator-=(const modint &o) noexcept { return *this = *this - o; }
  modint &operator*=(const modint &o) noexcept { return *this = *this * o; }
  modint &operator/=(const modint &o) { return *this = *this / o; }
  modint operator~() const noexcept { return pow(MODULO - 2); }
  modint operator-() const noexcept { return a ? modint(MODULO - a) : *this; }
  modint operator++() noexcept { return a == MODULO - 1 ? a = 0 : ++a, *this; }
  modint operator--() noexcept { return a ? --a : a = MODULO - 1, *this; }
  bool operator==(const modint &o) const noexcept { return a == o.a; }
  bool operator!=(const modint &o) const noexcept { return a != o.a; }
  bool operator<(const modint &o) const noexcept { return a < o.a; }
  bool operator<=(const modint &o) const noexcept { return a <= o.a; }
  bool operator>(const modint &o) const noexcept { return a > o.a; }
  bool operator>=(const modint &o) const noexcept { return a >= o.a; }
  explicit operator bool() const noexcept { return a; }
  explicit operator uint32() const noexcept { return a; }
  modint pow(uint32 x) const noexcept {
    uint64 t = a, u = 1;
    while (x) {
      if (x & 1) u = u * t % MODULO;
      t = (t * t) % MODULO;
      x >>= 1;
    }
    return modint(u);
  }
  uint32 get() const noexcept { return a; }
};
using mint = modint<MOD>;
class SCC {
 private:
  const int n;
  vector<vector<int>> G;
  vector<vector<int>> rG;
  vector<int> vs;
  vector<bool> used;
  vector<int> cmp;
  int sccsize_k;

 public:
  SCC(int _n) : n(_n), G(_n), rG(_n), used(_n), cmp(_n) {}
  void addEdge(int from, int to) {
    G[from].emplace_back(to);
    rG[to].emplace_back(from);
  }
  void dfs(int v) {
    used[v] = true;
    for (auto &&nxt : G[v]) {
      if (!used[nxt]) dfs(nxt);
    }
    vs.emplace_back(v);
  }
  void rdfs(int v, int k) {
    used[v] = true;
    cmp[v] = k;
    for (auto &&nxt : rG[v]) {
      if (!used[nxt]) rdfs(nxt, k);
    }
    vs.emplace_back(v);
  }
  int scc() {
    for (int v = 0; v < n; v++) {
      if (!used[v]) dfs(v);
    }
    used.assign(n, false);
    sccsize_k = 0;
    for (int i = vs.size() - 1; i >= 0; i--) {
      int v = vs[i];
      if (!used[v]) rdfs(v, sccsize_k++);
    }
    return sccsize_k;
  }
  bool same(int a, int b) { return cmp[a] == cmp[b]; }
  vector<int> get_color() { return cmp; }
};
vector<VVI> ForestToGraphs(vector<PII> &edge, int V) {
  SCC SccG(V);
  for (const auto &it : edge) {
    SccG.addEdge(it.first, it.second);
    SccG.addEdge(it.second, it.first);
  }
  int scc_sz = SccG.scc();
  VI color = SccG.get_color();
  vector<VVI> ret(scc_sz);
  map<PII, int> Map;
  map<int, int> CC;
  auto reid = [&Map, &CC](int c, int x) {
    if (Map.find(PII(c, x)) == Map.end()) {
      int nc = CC[c];
      Map[PII(c, x)] = nc;
      CC[c]++;
    }
    return Map[PII(c, x)];
  };
  vector<vector<PII>> edges(scc_sz);
  for (int(i) = (0); (i) < (int((edge).size())); (i)++) {
    int a, b;
    tie(a, b) = edge[i];
    int c = color[a];
    a = reid(c, a), b = reid(c, b);
    edges[c].push_back(PII(a, b));
  }
  for (int(i) = (0); (i) < (scc_sz); (i)++) {
    ret[i].resize(CC[i]);
    for (int(j) = (0); (j) < (int((edges[i]).size())); (j)++) {
      int a, b;
      tie(a, b) = edges[i][j];
      ret[i][a].push_back(b);
      ret[i][b].push_back(a);
    }
  }
  return ret;
}
int main() {
  int T = read();
  for (int(_) = (0); (_) < (T); (_)++) {
    LL N = read(), M = read();
    SCC SG(N);
    vector<PII> edge(M);
    for (int(i) = (0); (i) < (M); (i)++) {
      int a = read() - 1, b = read() - 1;
      edge[i] = PII(a, b);
    }
    vector<VVI> forest = ForestToGraphs(edge, N);
    int f = 1;
    mint ans = 1;
    for (int(j) = (0); (j) < (int((forest).size())); (j)++) {
      ;
      if (int((forest[j]).size()) == 0) {
        ans *= 3;
        ;
        continue;
      }
      VI res = isBipartiteGraph(forest[j]);
      if (int((res).size())) {
        int B = 0;
        for (int(i) = (0); (i) < (int((forest[j]).size())); (i)++) {
          if (res[i] == 1) {
            B++;
          }
        }
        int R = int((forest[j]).size()) - B;
        mint two = 2;
        mint ret = 0;
        ret += two.pow(R);
        ret += two.pow(B);
        ans *= ret;
      } else {
        f = 0;
      };
    }
    if (f) {
      cout << ans.get() << endl;
    } else {
      cout << 0 << endl;
    }
  }
  return 0;
}

```