VegiCat มีเมทริกซ์จำนวนเต็มขนาด $n \times n$ คือ $A = (a_{ij})$ สำหรับแต่ละ $1 \le i, j \le n$:

• หาก $i = j$, $i = 1$ หรือ $j = 1$ แล้ว $a_{ij} = -1$
• มิฉะนั้น $a_{ij}$ จะเป็นจำนวนเต็มไม่ลบ

จงช่วย VegiCat สร้างกราฟอย่างง่ายแบบไม่มีทิศทาง $G$ ที่มี $n$ จุดยอด โดยระบุหมายเลขตั้งแต่ $1$ ถึง $n$

สำหรับทุกคู่ของจุดยอดที่แตกต่างกัน $i, j$ ซึ่ง $i > 1$ และ $j > 1$ กราฟจะต้องสอดคล้องกับเงื่อนไขต่อไปนี้: หลังจากลบจุดยอด $i$ และ $j$ พร้อมกับเส้นเชื่อมทั้งหมดที่มีจุดปลายอยู่ที่จุดยอดใดจุดยอดหนึ่งในสองจุดนี้แล้ว จะต้องเหลือเส้นเชื่อมอยู่ $a_{ij}$ เส้นพอดี

จุดยอดแต่ละคู่ $i, j$ จะถูกพิจารณาแยกจากกัน กล่าวคือ สำหรับแต่ละคู่ ให้เริ่มต้นด้วยกราฟ $G$ ก่อนที่จะมีการลบจุดยอดหรือเส้นเชื่อมใด ๆ

รับประกันว่ามีกราฟดังกล่าวอย่างน้อยหนึ่งกราฟ หากมีหลายคำตอบ ให้แสดงคำตอบใดก็ได้

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 6 \cdot 10^4$) แทนจำนวนกรณีทดสอบ รายละเอียดของแต่ละกรณีทดสอบมีดังต่อไปนี้

สำหรับแต่ละกรณีทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็ม $n$ ($4 \le n \le 10^3$) แทนจำนวนจุดยอดในกราฟ

จากนั้นอีก $n$ บรรทัดถัดไป แต่ละบรรทัดประกอบด้วยจำนวนเต็ม $n$ ตัวที่คั่นด้วยช่องว่าง $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$) แทนเมทริกซ์ $A$ ที่อธิบายไว้ในโจทย์

รับประกันว่าผลรวมของ $n^2$ จากทุกกรณีทดสอบรวมกันไม่เกิน $1.2 \cdot 10^6$ และมีกราฟที่สอดคล้องกับเมทริกซ์ $A$ อย่างน้อยหนึ่งกราฟ

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้แสดงเมทริกซ์ประชิดของกราฟที่คุณสร้างขึ้น โดยแสดง $n$ บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็ม $n$ ตัวที่คั่นด้วยช่องว่าง จำนวนเต็มแต่ละตัวต้องเป็น $0$ หรือ $1$ เท่านั้น สมาชิกในแถวที่ $i$ และคอลัมน์ที่ $j$ มีค่าเป็น $1$ หากมีเส้นเชื่อมระหว่างจุดยอด $i$ และ $j$ และเป็น $0$ ในกรณีอื่น หากมีหลายคำตอบ ให้แสดงคำตอบใดก็ได้

ตัวอย่าง

ข้อมูลนำเข้า 1

2
5
-1 -1 -1 -1 -1
-1 -1  3  1  2
-1  3 -1  2  2
-1  1  2 -1  1
-1  2  2  1 -1
7
-1 -1 -1 -1 -1 -1 -1
-1 -1  4  5  3  6  5
-1  4 -1  5  4  5  5
-1  5  5 -1  5  7  5
-1  3  4  5 -1  4  4
-1  6  5  7  4 -1  5
-1  5  5  5  4  5 -1

ข้อมูลส่งออก 1

0 1 0 1 1
1 0 0 0 0
0 0 0 1 0
1 0 1 0 1
1 0 0 1 0
0 1 1 0 1 0 0
1 0 0 0 0 1 1
1 0 0 0 1 0 1
0 0 0 0 1 1 0
1 0 1 1 0 0 1
0 1 0 1 0 0 0
0 1 1 0 1 0 0

หมายเหตุ

เมทริกซ์ข้อมูลนำเข้าจริงจะมีช่องว่างเพียงช่องเดียวระหว่างจำนวนเต็มสองตัว ช่องว่างเพิ่มเติมในตัวอย่างถูกใส่ไว้เพื่อให้อ่านแผนผังได้ง่ายขึ้นเท่านั้น