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