description: 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
solution: import java.io.OutputStream;
  import java.io.IOException;
  import java.io.InputStream;
  import java.io.PrintWriter;
  import java.io.PrintStream;
  import java.util.Random;
  import java.util.TreeSet;
  import java.io.InputStream;
  
  /**
   * Built using CHelper plug-in
   * Actual solution is at the top
   *
   * @author sarthakmanna
   */
  public class Main {
      public static void main(String[] args) {
          InputStream inputStream = System.in;
          OutputStream outputStream = System.out;
          FastReader in = new FastReader(inputStream);
          PrintWriter out = new PrintWriter(outputStream);
          D2DominoHardVersion solver = new D2DominoHardVersion();
          int testCount = Integer.parseInt(in.next());
          for (int i = 1; i <= testCount; i++)
              solver.solve(i, in, out);
          out.close();
      }
  
      static class D2DominoHardVersion {
          final static Helper hp = new Helper();
          int N;
          int M;
          int K;
          char[][] G;
  
          public void solve(int testNumber, FastReader in, PrintWriter out) {
              int i, j, k;
  
              N = in.nextInt();
              M = in.nextInt();
              K = in.nextInt();
              G = new char[N][M];
  
              //Comparator<Pair<Integer, Integer>> com = (a, b) -> Integer.compare(a.getSecond(), b.getSecond());
              TreeSet<Pair<Integer, Integer>> oddHeight = new TreeSet<>();
              TreeSet<Pair<Integer, Integer>> evenHeight = new TreeSet<>();
              for (j = 0; j < M; ++j) {
                  if (N % 2 == 0) evenHeight.add(new Pair<>(j, 0));
                  else oddHeight.add(new Pair<>(j, 0));
              }
  
              while (K-- > 0) {
                  if (!oddHeight.isEmpty()) {
                      Pair<Integer, Integer> top = oddHeight.pollFirst();
                      int td = top.getSecond(), lr = top.getFirst();
                      Pair<Integer, Integer> expected = new Pair<>(lr + 1, td);
  
                      if (oddHeight.contains(expected)) {
                          oddHeight.remove(expected);
  
                          G[td][lr] = G[td][lr + 1] = findSuitableCharacter(td, lr, td, lr + 1);
  
                          if (++td < N) {
                              top.setSecond(td);
                              expected.setSecond(td);
  
                              evenHeight.add(top);
                              evenHeight.add(expected);
                          }
                      } else {
                          out.println("NO");
                          return;
                      }
                  } else {
                      Pair<Integer, Integer> top = evenHeight.pollFirst();
                      int td = top.getSecond(), lr = top.getFirst();
                      Pair<Integer, Integer> expected = new Pair<>(lr + 1, td);
  
                      if (evenHeight.contains(expected)) {
                          evenHeight.remove(expected);
  
                          G[td][lr] = G[td][lr + 1] = findSuitableCharacter(td, lr, td, lr + 1);
  
                          if (++td < N) {
                              top.setSecond(td);
                              expected.setSecond(td);
  
                              oddHeight.add(top);
                              oddHeight.add(expected);
                          }
                      } else {
                          out.println("NO");
                          return;
                      }
                  }
              }
  
              if (!oddHeight.isEmpty()) {
                  out.println("NO");
                  return;
              }
  
              for (i = 0; i < N; ++i)
                  for (j = 0; j < M; ++j)
                      if (G[i][j] == '\0') {
                          G[i][j] = G[i + 1][j] = findSuitableCharacter(i, j, i + 1, j);
                      }
  
              out.println("YES");
              //for (char[] row : G) out.println(new String(row));
          }
  
          int getChar(int i, int j) {
              if (i < 0 || j < 0 || i >= N || j >= M) return '\0';
              else return G[i][j];
          }
  
          char findSuitableCharacter(int i1, int j1, int i2, int j2) {
              while (true) {
                  char ret = (char) ('a' + hp.getRandomInRange(0, 25));
                  boolean ok = true;
                  for (int i = -1; i <= +1 && ok; ++i)
                      for (int j = -1; j <= +1 && ok; ++j) {
                          if (getChar(i + i1, j + j1) == ret || getChar(i + i2, j + j2) == ret) {
                              ok = false;
                          }
                      }
                  if (ok) return ret;
              }
          }
  
      }
  
      static class Helper {
          public final long MOD;
          public final int MAXN;
          final Random rnd;
  
          public Helper() {
              MOD = 1000_000_007;
              MAXN = 1000_006;
              rnd = new Random();
          }
  
          public Helper(long mod, int maxn) {
              MOD = mod;
              MAXN = maxn;
              rnd = new Random();
          }
  
          public int getRandomInRange(int l, int r) {
              return rnd.nextInt(r - l + 1) + l;
          }
  
          public int compare(Object a, Object b) {
              if (a instanceof Integer) {
                  return Integer.compare((Integer) a, (Integer) b);
              } else if (a instanceof Long) {
                  return Long.compare((Long) a, (Long) b);
              } else if (a instanceof String) {
                  return ((String) a).compareTo((String) b);
              } else if (a instanceof Float) {
                  return Float.compare((Float) a, (Float) b);
              } else if (a instanceof Double) {
                  return Double.compare((Double) a, (Double) b);
              } else {
                  return 5 / 0;
              }
          }
  
      }
  
      static class Pair<U, V> implements Comparable<Pair<U, V>> {
          U first;
          V second;
          Helper hp = new Helper();
  
          public Pair(U u, V v) {
              first = u;
              second = v;
          }
  
          public U getFirst() {
              return first;
          }
  
          public V getSecond() {
              return second;
          }
  
          public void setSecond(V second) {
              this.second = second;
          }
  
          public int compareTo(Pair<U, V> p) {
              int cmp = hp.compare(first, p.first);
              if (cmp == 0) {
                  cmp = hp.compare(second, p.second);
              }
              return cmp;
          }
  
          public String toString() {
              return "(" + first + ", " + second + ")";
          }
  
      }
  
      static class FastReader {
          static final int BUFSIZE = 1 << 20;
          static byte[] buf;
          static int index;
          static int total;
          static InputStream in;
  
          public FastReader(InputStream is) {
              try {
                  in = is;
                  buf = new byte[BUFSIZE];
              } catch (Exception e) {
              }
          }
  
          private int scan() {
              try {
                  if (index >= total) {
                      index = 0;
                      total = in.read(buf);
                      if (total <= 0)
                          return -1;
                  }
                  return buf[index++];
              } catch (Exception | Error e) {
                  System.err.println(e.getMessage());
                  return 13 / 0;
              }
          }
  
          public String next() {
              int c;
              for (c = scan(); c <= 32; c = scan()) ;
              StringBuilder sb = new StringBuilder();
              for (; c > 32; c = scan())
                  sb.append((char) c);
              return sb.toString();
          }
  
          public int nextInt() {
              int c, val = 0;
              for (c = scan(); c <= 32; c = scan()) ;
              boolean neg = c == '-';
              if (c == '-' || c == '+')
                  c = scan();
              for (; c >= '0' && c <= '9'; c = scan())
                  val = (val << 3) + (val << 1) + (c & 15);
              return neg ? -val : val;
          }
  
      }
  }
  
  