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].
5
68611840 10000000 60301
767316447 10000000 8468
430547866 10000000 0
552915811 10000000 0
295043473 10000000 0
 5
904980175 9999999 0
665518669 10000000 0
546981263 9999997 350538
623219061 9999996 486146
601826992 9999999 477243
 5
652664040 9088207 351721
838981402 9558163 949211
627901334 9007335 804267
124299440 9663383 0
91348615 9566236 0
 5
652664040 9088207 500534
347017246 9044258 319954
980053435 9837743 229781
414672186 9748315 461982
124299440 9663383 263491
 5
68611840 10000000 749119
85328351 10000000 993656
819226708 10000000 247193
755441322 10000000 740194
804601099 10000000 250256
 5
904980175 9999999 6788
665518669 10000000 832563
546981263 9999997 827417
961093238 9999996 517261
692801443 9999996 59567

350759062
640747647
0
0
0
 0
0
416087444
361743271
148269437
 759534327
323113303
534607258
0
0
 759534327
279467561
696669698
758867258
205998803
 350759062
485561434
207606140
949931760
923189885
 279412901
37810566
416087444
294263281
890982526

#include <bits/stdc++.h>
using namespace std;
inline int read() {
  char ch = getchar();
  int nega = 1;
  while (!isdigit(ch)) {
    if (ch == '-') nega = -1;
    ch = getchar();
  }
  int ans = 0;
  while (isdigit(ch)) {
    ans = ans * 10 + ch - 48;
    ch = getchar();
  }
  if (nega == -1) return -ans;
  return ans;
}
void print(vector<int> x) {
  for (int i = 0; i < (int)x.size(); i++)
    printf("%d%c", x[i], " \n"[i == (int)x.size() - 1]);
}
inline int add(int x, int y) {
  return x + y >= 998244353 ? x + y - 998244353 : x + y;
}
inline int add(int x, int y, int z) { return add(add(x, y), z); }
inline int sub(int x, int y) { return x - y < 0 ? x - y + 998244353 : x - y; }
inline int mul(int x, int y) { return 1LL * x * y % 998244353; }
inline int mul(int x, int y, int z) { return mul(mul(x, y), z); }
int qpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x);
    x = mul(x, x);
    y >>= 1;
  }
  return ans;
}
int Inv(int x) { return qpow(x, 998244353 - 2); }
int pw[10000005], res[10000005], co[10000005];
void work() {
  int n = read(), k = read(), x = read();
  if (x == 0) {
    if (n > k)
      printf("0\n");
    else {
      int ans = 1;
      for (int i = 0; i < n; i++) ans = mul(ans, sub(pw[k], pw[i]));
      printf("%d\n", ans);
    }
  } else {
    int ans = 0, c = qpow(2, n);
    res[0] = pw[k - 1] - 1;
    for (int i = 1; i < k; i++) res[i] = mul(res[i - 1], pw[k - i - 1] - 1);
    co[0] = 1;
    for (int i = 1; i <= k; i++) co[i] = mul(co[i - 1], c);
    for (int i = 0; i < k; i++) {
      int r = mul(co[k - i - 1], i ? res[i - 1] : 1, pw[k - i - 1]);
      if (i & 1)
        ans = sub(ans, r);
      else
        ans = add(ans, r);
    }
    printf("%d\n", ans);
  }
}
signed main() {
  pw[0] = 1;
  for (int i = 1; i < 10000005; i++) pw[i] = add(pw[i - 1], pw[i - 1]);
  int T = read();
  while (T--) work();
  return 0;
}
