The only difference between this problem and D2 is that you don't have to provide the way to construct the answer in this problem, but you have to do it in D2.

There's a table of n × m cells (n rows and m columns). The value of n ⋅ m is even.

A domino is a figure that consists of two cells having a common side. It may be horizontal (one of the cells is to the right of the other) or vertical (one of the cells is above the other).

You need to find out whether it is possible to place nm/2 dominoes on the table so that exactly k of them are horizontal and all the other dominoes are vertical. The dominoes cannot overlap and must fill the whole table.

Input

The first line contains one integer t (1 ≤ t ≤ 10) — the number of test cases. Then t test cases follow.

Each test case consists of a single line. The line contains three integers n, m, k (1 ≤ n,m ≤ 100, 0 ≤ k ≤ nm/2, n ⋅ m is even) — the number of rows, columns and horizontal dominoes, respectively.

Output

For each test case output "YES", if it is possible to place dominoes in the desired way, or "NO" otherwise.

You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

Example

Input


8
4 4 2
2 3 0
3 2 3
1 2 0
2 4 2
5 2 2
2 17 16
2 1 1


Output


YES
YES
YES
NO
YES
NO
YES
NO
1
6 7 20
 10
26 80 521
34 14 232
62 66 767
80 72 2664
70 50 461
85 92 108
59 44 732
55 6 13
47 22 504
79 16 8
 10
8 67 208
87 58 1834
96 82 2079
98 54 1497
31 58 190
57 86 1508
76 79 3000
87 8 24
76 11 129
80 62 51
 1
3 2 1
 10
88 89 596
10 45 47
77 90 3041
53 32 557
12 33 194
80 52 57
90 14 324
29 42 371
11 12 42
60 32 414
 10
8 5 8
7 4 0
10 10 47
5 2 2
6 3 2
8 4 7
10 4 20
2 6 5
3 8 9
9 8 32
 1
38 1 10
 10
3 2 1
4 5 2
4 6 10
4 6 1
4 6 8
4 1 0
1 4 1
8 5 3
1 4 0
5 4 2
 1
2 1 0
 1
1 10 5
 10
73 70 591
53 94 571
9 14 7
6 70 200
18 38 42
24 30 141
84 93 3253
27 30 20
81 32 535
77 30 65
 1
6 3 8
 1
3 20 24
 10
2 30 28
2 30 29
2 30 30
3 2 0
3 2 1
3 2 2
3 2 3
3 4 0
3 4 1
3 4 2
 10
19 54 198
100 34 1421
1 2 1
73 32 919
68 15 450
100 97 344
74 70 857
22 25 49
92 45 1096
70 95 2489
 10
10 44 115
81 56 1578
80 60 6
32 15 217
98 35 664
70 97 2635
11 56 20
52 1 0
8 8 11
98 25 673
 10
61 24 9
62 53 1271
73 64 165
18 48 376
14 59 413
56 64 526
60 58 1092
13 38 177
1 28 14
69 52 948
 10
2 1 0
2 1 1
2 2 0
2 2 1
2 2 2
2 3 0
2 3 1
2 3 2
2 3 3
2 4 0
 10
4 1 1
10 2 2
2 1 1
5 2 2
5 6 8
2 2 1
1 32 8
11 2 3
2 17 16
2 7 3
 4
46 99 44
46 57 26
4 3 2
1 100 50
 4
19 78 491
4 30 44
62 49 1130
44 58 950
 10
45 42 720
93 90 2262
41 100 1529
67 56 970
69 56 150
88 46 1754
67 82 1520
76 87 159
96 2 91
15 70 110
 1
8 5 2
 1
3 6 1
 10
24 77 876
57 66 288
25 38 14
32 51 752
64 87 1389
90 10 8
5 68 152
7 86 238
9 72 6
84 52 196
 1
3 4 2
 10
91 48 24
99 100 98
1 100 50
2 1 0
100 1 0
1 2 0
70 75 2592
4 5 10
99 98 47
91 60 2395
 6
9 4 12
10 3 14
9 10 15
4 8 7
5 2 0
10 2 3
 8
99 100 98
1 100 50
2 1 0
100 1 0
1 2 0
70 75 2592
4 5 10
99 98 47
 10
13 80 309
77 40 1074
9 76 195
67 16 193
60 55 237
14 13 56
96 63 1195
4 1 0
66 4 71
12 30 58
 1
82 1 24
 2
2 1 0
10 1 0
 1
73 34 11
 9
99 100 98
1 100 50
2 1 0
100 1 0
1 2 0
70 75 2592
4 5 10
99 98 47
91 60 2395
 4
1 100 50
1 2 0
70 75 2592
4 5 10
 4
1 8 0
1 8 4
8 1 0
8 1 4
 1
20 19 186
 10
39 70 1166
87 70 2366
23 92 685
60 58 918
67 56 957
89 34 251
78 18 186
40 87 6
79 90 3209
21 94 963
 10
4 2 0
4 2 1
4 2 2
4 2 3
4 2 4
4 3 0
4 3 1
4 3 2
4 3 3
4 3 4
 1
4 1 0
 10
2 30 26
2 30 27
2 30 28
2 30 29
2 30 30
3 2 0
3 2 1
3 2 2
3 2 3
3 4 0
 10
77 66 1498
76 89 2399
70 80 645
77 18 638
32 88 676
23 84 61
16 94 99
3 6 4
75 66 574
1 72 36
 10
33 70 810
98 79 1630
7 98 217
57 58 1405
86 48 1182
59 44 624
14 16 100
14 26 108
40 51 1004
42 61 876
 1
83 22 11
 1
3 8 5
 10
92 11 0
27 22 0
18 26 0
81 88 0
24 6 0
100 61 3050
48 9 216
20 32 320
82 64 2624
28 23 322
 10
10 59 118
100 76 1379
85 48 1664
67 44 150
71 70 2018
67 28 409
52 9 72
57 84 2099
49 94 1033
1 6 3
 1
1 4 2
 10
5 52 84
28 50 393
69 26 716
37 2 1
79 100 235
1 18 3
61 68 1385
88 42 1668
23 62 33
36 27 410
 10
1 10 2
1 10 3
1 10 4
1 10 5
1 12 0
1 12 1
1 12 2
1 12 3
1 12 4
1 12 5
 1
74 3 92
 10
70 54 890
38 26 490
6 90 72
44 87 1492
80 14 279
76 4 15
21 4 42
92 2 73
51 58 91
28 52 485
 1
3 8 2
 7
1 6 3
4 1 2
6 1 2
8 1 2
8 1 4
10 1 2
10 1 4
 10
1 6 3
98 13 376
62 84 680
65 16 440
74 94 93
85 82 1895
58 49 656
44 56 604
47 90 1568
73 80 99
 10
100 100 5000
100 100 5000
100 100 5000
100 100 5000
100 100 5000
100 100 5000
100 100 5000
100 100 5000
100 100 5000
100 100 5000
 1
32 1 8
 1
1 2 1
 10
66 50 699
67 72 4
20 68 63
67 60 1165
79 84 734
29 94 1352
57 8 178
38 77 640
56 77 37
98 20 564
 8
32 1 8
2 1 0
17 22 3
1 6 3
3 4 2
5 6 5
6 3 8
6 5 14
 5
1 2 1
2 1 0
2 1 1
5 6 2
6 5 14
 1
8 3 10
 1
1 6 3
 1
6 3 2
 10
1 2 0
1 2 1
1 4 0
1 4 1
1 4 2
1 6 0
1 6 1
1 6 2
1 6 3
1 8 0
 10
1 10 1
1 10 2
1 10 3
1 10 4
1 10 5
1 12 0
1 12 1
1 12 2
1 12 3
1 12 4
 1
6 1 2
 10
44 86 670
29 48 144
61 80 1446
3 54 27
9 44 189
84 23 408
11 96 134
54 99 448
75 24 434
63 34 222
 1
8 1 0
 10
54 91 1578
86 10 248
28 67 460
77 74 523
46 26 28
74 9 292
93 2 1
46 77 675
95 16 517
4 89 95
 10
77 4 134
43 16 48
95 10 436
33 16 7
54 95 65
32 67 279
24 37 181
11 24 38
82 89 3250
45 90 967
 10
16 15 45
78 93 1360
37 98 964
20 95 78
63 14 362
6 11 13
10 1 0
77 38 1276
30 3 11
68 62 1558
 1
5 24 10
 2
62 22 678
32 49 757
 1
86 51 2176
 1
7 4 2
 10
88 39 184
5 62 28
85 50 335
30 79 754
99 74 2722
63 24 332
63 60 1537
36 30 505
76 39 485
1 4 2
 10
1 2 1
86 32 251
24 29 69
12 9 52
41 16 127
52 57 934
36 17 137
8 20 10
83 92 2423
99 70 2260
 10
17 30 107
32 89 1016
43 76 142
67 24 329
42 98 1805
2 1 0
31 18 176
35 90 1089
83 30 360
77 80 1546
 10
63 72 186
44 54 823
44 92 369
38 39 274
29 76 818
21 16 88
78 35 1358
50 81 1175
54 7 107
94 31 1121
 7
2 1 0
8 5 5
8 1 4
7 2 3
1 6 3
10 3 3
7 10 17
 10
5 98 134
31 18 26
68 75 2113
49 66 571
7 64 67
1 32 15
74 91 919
73 90 7
10 22 15
51 30 150
 7
1 100 50
2 1 0
100 1 0
1 2 0
70 75 2592
4 5 10
99 98 47
 3
6 1 0
2 7 4
10 2 10
 1
5 4 2
 10
90 100 275
91 94 3004
91 92 3256
92 95 3437
90 98 1697
100 92 3721
94 92 3025
94 100 1226
96 98 1608
94 98 3521
 1
60 1 0
 8
6 6 17
7 6 2
2 5 0
2 2 1
1 2 1
10 6 11
7 8 2
1 2 1
 10
100 100 1345
100 100 4048
100 100 4406
100 100 4403
100 100 1455
100 100 3091
100 100 2074
100 100 2193
100 100 1845
100 100 675
 10
7 20 6
85 92 2190
7 24 25
76 8 113
35 68 305
72 49 1649
93 18 773
20 90 547
89 84 1944
75 52 104
 1
6 1 0

NO
 NO
YES
NO
YES
NO
YES
YES
YES
NO
YES
 YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
 YES
 YES
NO
YES
NO
NO
NO
YES
YES
YES
YES
 YES
NO
NO
NO
YES
NO
YES
NO
NO
YES
 NO
 YES
YES
YES
NO
YES
YES
NO
NO
NO
YES
 YES
 YES
 YES
YES
YES
YES
YES
NO
NO
NO
NO
YES
 NO
 YES
 YES
NO
YES
NO
YES
NO
YES
NO
NO
YES
 NO
NO
YES
NO
YES
YES
NO
NO
YES
NO
 NO
YES
YES
NO
YES
NO
NO
YES
NO
NO
 NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
 YES
NO
YES
NO
YES
YES
NO
YES
NO
YES
 NO
YES
NO
NO
NO
NO
NO
YES
YES
NO
 YES
YES
YES
YES
 YES
YES
YES
YES
 NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
 YES
 NO
 YES
NO
NO
YES
NO
YES
YES
NO
NO
YES
 YES
 YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
 YES
NO
YES
NO
NO
NO
 YES
YES
YES
YES
NO
NO
NO
NO
 NO
YES
NO
NO
NO
YES
NO
YES
NO
YES
 NO
 YES
YES
 NO
 YES
YES
YES
YES
NO
NO
NO
NO
NO
 YES
NO
NO
NO
 NO
YES
YES
NO
 NO
 NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
 YES
NO
YES
NO
YES
YES
NO
YES
NO
YES
 YES
 YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
 NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
 NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
 YES
 NO
 YES
NO
YES
NO
YES
NO
NO
YES
YES
NO
 YES
NO
YES
YES
NO
NO
YES
NO
YES
YES
 YES
 YES
NO
NO
YES
NO
NO
NO
YES
YES
YES
 NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
 NO
 YES
YES
YES
YES
NO
NO
YES
NO
YES
NO
 NO
 YES
NO
NO
NO
NO
NO
NO
 YES
YES
YES
YES
NO
YES
YES
YES
NO
NO
 YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
 NO
 YES
 NO
NO
NO
NO
YES
NO
YES
YES
NO
YES
 NO
YES
NO
YES
YES
YES
NO
NO
 YES
YES
NO
NO
NO
 NO
 YES
 YES
 NO
YES
NO
NO
YES
NO
NO
NO
YES
NO
 NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
 NO
 YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
 YES
 YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
 YES
YES
NO
NO
NO
NO
NO
YES
YES
YES
 NO
YES
NO
YES
NO
NO
YES
NO
NO
YES
 NO
 YES
NO
 NO
 YES
 YES
NO
YES
YES
NO
YES
NO
NO
NO
YES
 YES
NO
NO
NO
NO
YES
NO
YES
NO
NO
 YES
YES
YES
NO
NO
YES
NO
YES
NO
YES
 YES
NO
NO
YES
YES
YES
NO
NO
NO
NO
 YES
NO
NO
YES
YES
NO
YES
 NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
 YES
YES
YES
NO
NO
NO
NO
 YES
YES
YES
 YES
 NO
NO
YES
NO
NO
NO
NO
YES
YES
NO
 YES
 NO
NO
YES
NO
YES
NO
NO
YES
 NO
YES
YES
NO
NO
NO
YES
NO
NO
NO
 NO
YES
NO
NO
NO
NO
YES
NO
YES
YES
 YES

#include <bits/stdc++.h>
using namespace std;
char en = '\n';
void fileIO() {}
const long long MOD = 1e12;
long long first, n, m, k;
void solve() {
  cin >> n >> m >> k;
  first = 0;
  if (n % 2 && m % 2 == 0) {
    if ((2 * k) % m == 0 && ((2 * k) / m) % 2) first = 1;
  } else if (n % 2 == 0) {
    for (long long i = 0; i <= n; i += 2) {
      for (long long j = 1; j < (m) / 2 + 1; j++)
        if (i * j == k) first = 1;
    }
  }
  if (first)
    cout << "YES";
  else
    cout << "NO";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  fileIO();
  long long t = 1;
  cin >> t;
  while (t--) {
    solve();
    cout << en;
  }
  cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
  return 0;
}
