F. Painting Squares
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Aniol has a grid of white squares with dimensions $$$n \times m$$$. He can paint some of these squares black, but he can only perform two types of operations to paint the squares: paint an entire row black or paint an entire column black.

His three little cousins want to play a game. Each of them, including Aniol, thinks of an integer $$$a_i$$$, between $$$2$$$ and $$$2^{15}$$$. They then calculate $$$k = a_1 \cdot a_2 \cdot a_3 \cdot a_4$$$. Aniol wins if he can ensure that exactly $$$k$$$ white squares remain by only using the previous operations.

Input

The input starts with an integer $$$t$$$ indicating the number of test cases.

Each case consists of three integers $$$n$$$, $$$m$$$, and $$$k$$$.

Output

For each case, write a line with "SI" if it is possible to achieve this or "NO" otherwise. In both cases, you must write the answer without quotes.

Scoring

$$$1 \leq t \leq 30000$$$

$$$8 \leq k \leq n \cdot m$$$

$$$k = a_1 \cdot a_2 \cdot a_3 \cdot a_4$$$ with $$$2 \leq a_i \leq 2^{15}$$$

4 Points: $$$1 \leq n,m \leq 2^{c}$$$

There are 25 test files, each test file gives 4 points. For each file, $$$c$$$ takes a different value, ranging from 6 to 30.

Example
Input
3
2 50 81
29 22 546
27 13 168
Output
NO
SI
SI