toberu cần gạch để xây dựng Instafeed của mình. Cậu cần ~n~ viên gạch, viên gạch thứ ~i~ có độ đẹp là ~a_i~. Các viên gạch không được có cùng độ đẹp, vì toberu không muốn xem lại cùng một loại Instareel.

Ngoài ra, cậu có thêm ~m~ yêu cầu dưới dạng ~(i, j)~ (~1 \le i < j \le n~), tức tích độ đẹp của viên gạch thứ ~i~ và ~j~ (hay ~a_i \times a_j~) là số chính phương.

Hãy xây giúp toberu một Instafeed như vậy!

toberu sẽ nhờ bạn xây dựng ~t~ Instafeed với ~n~ và ~m~ riêng biệt. Bạn cần trả lời ~t~ câu hỏi của cậu với dãy ~a~ tương ứng.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 1000~) là số lượng test.

Mỗi test gồm:

• Dòng đầu tiên chứa hai số nguyên không âm ~n~ và ~m~ (~2 \le n \le 10^5~, ~0 \le m \le 10^5~) là số viên gạch và số yêu cầu.
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~(i, j)~ (~1 \le i, j \le n~) mô tả một điều kiện.

Dữ liệu đảm bảo tổng của ~n~ và tổng của ~m~ qua mọi test ~\le 10^5~.

OUTPUT

Với mỗi test, in ra dãy gạch ~a~ bạn tìm được. Bạn cần đảm bảo ~1 \le a_i \le 10^{18}~ (Vì gạch mà đẹp quá thì toberu không xem nổi).

Nếu không có dãy nào thỏa mãn, hoặc chỉ tồn tại một dãy với ít nhất một phần tử ~> 10^{18}~, in ra ~-1~ trên một dòng.

Nếu có nhiều dãy thỏa mãn, in ra dãy bất kỳ.

SAMPLE INPUT

2
3 1
1 2
4 3
1 2
3 4
1 3

SAMPLE OUTPUT

2 8 9
2 8 18 32