#include <bits/stdc++.h>
template <unsigned P>
class modint {
  static_assert(1 <= P);
  using mint = modint<P>;

 protected:
  unsigned v;

 public:
  modint() : v() {}
  template <typename T, typename std::enable_if<std::is_signed<T>::value &&
                                                    std::is_integral<T>::value,
                                                bool>::type = true>
  modint(T _v) {
    long long tmp = _v % static_cast<long long>(P);
    if (tmp < 0) {
      tmp += P;
    }
    v = tmp;
  }
  template <typename T, typename std::enable_if<std::is_unsigned<T>::value &&
                                                    std::is_integral<T>::value,
                                                bool>::type = true>
  modint(T _v) {
    v = _v % P;
  }
  unsigned val() const { return v; }
  static constexpr unsigned mod() { return P; }
  static mint raw(unsigned v) {
    mint res;
    res.v = v;
    return res;
  }
  mint &operator+=(const mint &rhs) {
    v < P - rhs.v ? v += rhs.v : v -= P - rhs.v;
    return *this;
  }
  mint &operator++() {
    v + 1 < P ? ++v : v = 0;
    return *this;
  }
  mint operator++(int) {
    mint tmp = *this;
    v + 1 < P ? ++v : v = 0;
    return tmp;
  }
  mint &operator-=(const mint &rhs) {
    v < rhs.v ? v += P - rhs.v : v -= rhs.v;
    return *this;
  }
  mint &operator--() {
    v == 0 ? v = P - 1 : --v;
    return *this;
  }
  mint operator--(int) {
    mint tmp = *this;
    v == 0 ? v = P - 1 : --v;
    return tmp;
  }
  mint operator-() const {
    mint res;
    res.v = v == 0 ? 0 : P - v;
    return res;
  }
  mint &operator*=(const mint &rhs) {
    v = static_cast<unsigned long long>(v) * rhs.v % P;
    return *this;
  }
  mint pow(unsigned long long b) const {
    mint a(*this), s(1);
    for (; b; b >>= 1) {
      if (b & 1) {
        s *= a;
      }
      a *= a;
    }
    return s;
  }
  mint inv() const { return pow(P - 2); }
  friend mint operator+(const mint &lhs, const mint &rhs) {
    return mint(lhs) += rhs;
  }
  friend mint operator-(const mint &lhs, const mint &rhs) {
    return mint(lhs) -= rhs;
  }
  friend mint operator*(const mint &lhs, const mint &rhs) {
    return mint(lhs) *= rhs;
  }
  friend bool operator==(const mint &lhs, const mint &rhs) {
    return lhs.v == rhs.v;
  }
  friend bool operator!=(const mint &lhs, const mint &rhs) {
    return lhs.v != rhs.v;
  }
  friend std::istream &operator>>(std::istream &in, mint &x) {
    return in >> x.v;
  }
  friend std::ostream &operator<<(std::ostream &out, const mint &x) {
    return out << x.v;
  }
};
using mint = modint<998244353>;
const mint mi2 = mint(2), minv2 = mi2.inv();
void solve() {
  int n, k, x;
  std::cin >> n >> k >> x;
  if (x == 0) {
    if (n > k) {
      std::cout << 0 << "\n";
      return;
    }
    mint pw = mi2.pow(k), now = 1;
    mint ans = 1;
    for (int i = 0; i < n; ++i) {
      ans *= pw - now;
      now += now;
    }
    std::cout << ans << "\n";
    return;
  }
  mint pw = mi2.pow(k), pwn = pw.pow(n), inv = minv2.pow(n);
  mint now = 1;
  mint ans = 0;
  for (int i = 0; i < k; ++i) {
    pw *= minv2;
    pwn *= inv;
    ans += pwn * now * pw;
    now *= 1 - pw;
  }
  std::cout << ans << "\n";
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int T;
  std::cin >> T;
  while (T--) {
    solve();
  }
}

### Prompt

Construct a CPP code solution to the problem outlined:

It was October 18, 2017. Shohag, a melancholic soul, made a strong determination that he will pursue Competitive Programming seriously, by heart, because he found it fascinating. Fast forward to 4 years, he is happy that he took this road. He is now creating a contest on Codeforces. He found an astounding problem but has no idea how to solve this. Help him to solve the final problem of the round.

You are given three integers n, k and x. Find the number, modulo 998 244 353, of integer sequences a_1, a_2, …, a_n such that the following conditions are satisfied: 

  * 0 ≤ a_i < 2^k for each integer i from 1 to n. 
  * There is no non-empty subsequence in a such that the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of the elements of the subsequence is x. 



A sequence b is a subsequence of a sequence c if b can be obtained from c by deletion of several (possibly, zero or all) elements.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^5) — the number of test cases.

The first and only line of each test case contains three space-separated integers n, k, and x (1 ≤ n ≤ 10^9, 0 ≤ k ≤ 10^7, 0 ≤ x < 2^{\operatorname{min}(20, k)}).

It is guaranteed that the sum of k over all test cases does not exceed 5 ⋅ 10^7.

Output

For each test case, print a single integer — the answer to the problem.

Example

Input


6
2 2 0
2 1 1
3 2 3
69 69 69
2017 10 18
5 7 0


Output


6
1
15
699496932
892852568
713939942

Note

In the first test case, the valid sequences are [1, 2], [1, 3], [2, 1], [2, 3], [3, 1] and [3, 2].

In the second test case, the only valid sequence is [0, 0].

### Response

```cpp
#include <bits/stdc++.h>
template <unsigned P>
class modint {
  static_assert(1 <= P);
  using mint = modint<P>;

 protected:
  unsigned v;

 public:
  modint() : v() {}
  template <typename T, typename std::enable_if<std::is_signed<T>::value &&
                                                    std::is_integral<T>::value,
                                                bool>::type = true>
  modint(T _v) {
    long long tmp = _v % static_cast<long long>(P);
    if (tmp < 0) {
      tmp += P;
    }
    v = tmp;
  }
  template <typename T, typename std::enable_if<std::is_unsigned<T>::value &&
                                                    std::is_integral<T>::value,
                                                bool>::type = true>
  modint(T _v) {
    v = _v % P;
  }
  unsigned val() const { return v; }
  static constexpr unsigned mod() { return P; }
  static mint raw(unsigned v) {
    mint res;
    res.v = v;
    return res;
  }
  mint &operator+=(const mint &rhs) {
    v < P - rhs.v ? v += rhs.v : v -= P - rhs.v;
    return *this;
  }
  mint &operator++() {
    v + 1 < P ? ++v : v = 0;
    return *this;
  }
  mint operator++(int) {
    mint tmp = *this;
    v + 1 < P ? ++v : v = 0;
    return tmp;
  }
  mint &operator-=(const mint &rhs) {
    v < rhs.v ? v += P - rhs.v : v -= rhs.v;
    return *this;
  }
  mint &operator--() {
    v == 0 ? v = P - 1 : --v;
    return *this;
  }
  mint operator--(int) {
    mint tmp = *this;
    v == 0 ? v = P - 1 : --v;
    return tmp;
  }
  mint operator-() const {
    mint res;
    res.v = v == 0 ? 0 : P - v;
    return res;
  }
  mint &operator*=(const mint &rhs) {
    v = static_cast<unsigned long long>(v) * rhs.v % P;
    return *this;
  }
  mint pow(unsigned long long b) const {
    mint a(*this), s(1);
    for (; b; b >>= 1) {
      if (b & 1) {
        s *= a;
      }
      a *= a;
    }
    return s;
  }
  mint inv() const { return pow(P - 2); }
  friend mint operator+(const mint &lhs, const mint &rhs) {
    return mint(lhs) += rhs;
  }
  friend mint operator-(const mint &lhs, const mint &rhs) {
    return mint(lhs) -= rhs;
  }
  friend mint operator*(const mint &lhs, const mint &rhs) {
    return mint(lhs) *= rhs;
  }
  friend bool operator==(const mint &lhs, const mint &rhs) {
    return lhs.v == rhs.v;
  }
  friend bool operator!=(const mint &lhs, const mint &rhs) {
    return lhs.v != rhs.v;
  }
  friend std::istream &operator>>(std::istream &in, mint &x) {
    return in >> x.v;
  }
  friend std::ostream &operator<<(std::ostream &out, const mint &x) {
    return out << x.v;
  }
};
using mint = modint<998244353>;
const mint mi2 = mint(2), minv2 = mi2.inv();
void solve() {
  int n, k, x;
  std::cin >> n >> k >> x;
  if (x == 0) {
    if (n > k) {
      std::cout << 0 << "\n";
      return;
    }
    mint pw = mi2.pow(k), now = 1;
    mint ans = 1;
    for (int i = 0; i < n; ++i) {
      ans *= pw - now;
      now += now;
    }
    std::cout << ans << "\n";
    return;
  }
  mint pw = mi2.pow(k), pwn = pw.pow(n), inv = minv2.pow(n);
  mint now = 1;
  mint ans = 0;
  for (int i = 0; i < k; ++i) {
    pw *= minv2;
    pwn *= inv;
    ans += pwn * now * pw;
    now *= 1 - pw;
  }
  std::cout << ans << "\n";
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int T;
  std::cin >> T;
  while (T--) {
    solve();
  }
}

```