ל-VegiCat יש מטריצת מספרים שלמים $A = (a_{ij})$ בגודל $n \times n$. עבור כל $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$ אחרת. אם ישנם מספר פתרונות, הדפיסו אחד מהם.

Examples

Input 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

Output 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

Note

במטריצת הקלט בפועל יהיה רווח בודד בלבד בין שני מספרים שלמים. הרווחים הנוספים בדוגמה נועדו לשפר את קריאות הפריסה.