You receive ~M~ queries with the form of ~(x,y)~. Find a sequence of size ~N~, formed with a's and b's where you must "find" each query. A query is found if you can find a substring with ~x~ a's and ~y~ b's.

Input Specification

On the first line you will find the number of test cases, ~T~ ~(1 \le T \le 50)~.
For each test case, you will find on the first line ~N~ and ~M~ ~(1 \le N \le 50, 1 \le M \le 500)~.
On the next ~M~ lines, you will find the queries with the space-separated integers ~x~ and ~y~.

Output Specification

For each test case, print a sequence which respects the requirement. If you can't find a sequence, print -1.

Sample Input

1
7 2
4 2
3 3

Sample Output

abaabab