لدى 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$ خلاف ذلك. إذا كانت هناك عدة حلول، فاطبع أيًا منها.

أمثلة

الإدخال 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

ملاحظة

ستحتوي مصفوفة الإدخال الفعلية على مسافة واحدة فقط بين كل عددين صحيحين. المسافات الإضافية في المثال وُضعت لتحسين وضوح العرض وقابليته للقراءة.