Given a matrix of size and two integers , determine weither it is possible to make all entrys of zero by repeatedly choosing submatrices and reduce the values in the chosen matrices by 1. If possible, print "^_^" in one line, or print "QAQ" in one line.

输入描述:

The first line contains one integer , denoting the number of test cases.

For each test case:

The first line contains four integers , denoting the size of given matrix and the size of chosen submatrices respectively.

The next  lines each contains  integers , denoting the entrys of matrix .

It's guaranteed that .

输出描述:

Print  lines each containing a string "^_^" or "QAQ", denoting the answer to each test case.

2
2 2 1 2
1 2
1 2
2 3 1 2
1 2 1
1 2 1

QAQ
^_^

For the second case, one possible scheme is to choose  respectively.