Bajtazar 订购了 $N$ 件新家具，并希望将它们全部摆放在他的客厅里。客厅是一个尺寸为 $A \times B$ 的矩形。每件家具也是一个矩形，第 $i$ 件家具的尺寸为 $c_i \times d_i$。

每件家具必须靠在长度为 $A$ 的墙壁之一放置，且其长度为 $c_i$ 的边必须与该墙壁齐平。当然，任意两件家具不得重叠；它们最多只能在边或角上接触。

请编写一个程序，帮助 Bajtazar 判断是否可以将所有 $N$ 件家具都摆放在他的客厅里。

你需要解决 $T$ 个独立的测试用例。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 30$)，表示测试用例的数量。

每个测试用例的第一行包含三个整数 $A, B, N$ ($1 \le A, B \le 10^6$, $1 \le N \le 1000$)，分别表示 Bajtazar 客厅的尺寸和家具的数量。接下来的 $N$ 行中，每行包含两个整数 $c_i, d_i$ ($1 \le c_i \le A, 1 \le d_i \le B$)，表示第 $i$ 件家具的尺寸。

所有测试用例中 $N$ 的总和不超过 $1000$。

输出格式

输出 $T$ 行。对于第 $i$ 个测试用例，如果可以将所有家具摆放好，则输出 TAK（波兰语中的“是”），否则输出 NIE（波兰语中的“否”）。

样例

样例输入 1

4
9 7 6
2 2
3 2
4 5
1 5
1 3
6 2
3 3 3
3 1
1 1
3 1
3 3 3
1 3
1 3
1 3
3 3 2
2 2
2 2

样例输出 1

TAK
NIE
TAK
NIE

说明

样例解释：第一个测试用例中家具的一种有效摆放方式如下图所示：