You have a keyboard with only the digit keys $0, 1, 2, \dots, 9$. For any positive integer $m$, it is obvious that you can always press a positive integer that is a multiple of $m$. Now, $k$ of your digit keys have been removed, but you still want to press a positive integer that is a multiple of $m$.

Input

Each test case contains multiple test data. The first line contains an integer $T$ ($1 \le T \le 5 \times 10^4$), representing the number of test cases.

For each test case: The first line contains two positive integers $m, k$ ($1 \le m \le 10^7, 0 \le k \le 9$), representing that after $k$ keys are removed, you need to press a positive integer that is a multiple of $m$. The second line contains $k$ distinct positive integers $p_i$ ($1 \le p_i \le 9$), representing the removed keys.

Output

For each test case: If a solution exists, output your operations as a sequence of "press digit $a$ for $b$ times": The first line outputs an integer $n$, where $1 \le n \le 100$, representing the number of operations you perform. The next $n$ lines each output two integers $a, b$, where $0 \le a \le 9, 1 \le b \le 10^{18}$, representing one operation of "press digit $a$ for $b$ times". If no solution exists, output a single line containing $-1$.

Examples

Input 1

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

Output 1

2
1 3
0 1
-1

Note

For the first test case in the example, the positive integer pressed by the operations in the sample output is $1110$, and $1110 = 37 \times 30$, which is a multiple of $37$.