Hài lòng với những Instafeed bạn đã xây ở bản dễ, toberu muốn nhờ bạn nốt ~t~ câu hỏi nữa:

Dựng một Instafeed với ~n~ viên gạch bất kỳ, viên gạch thứ ~i~ có độ đẹp là ~a_i~, để thỏa mãn ~m~ yêu cầu dưới dạng ~(i, j)~ (~1 \le i, j \le n~), tức ~a_i~ chia hết cho ~a_j~.

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~ (~1 \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 yêu cầu.

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, hay chỉ tồn tại dãy sao cho có ít nhất một viên gạch có độ đẹp ~> 10^{18}~, hãy in ra ~-1~.

SAMPLE INPUT

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

SAMPLE OUTPUT

100 50 25 10
10 2 3 5 1