כידוע, לבעיית ה-APSP (המסלולים הקצרים ביותר בין כל הזוגות) יש קשר עמוק לכפל מטריצות min+. היום, אנו רוצים שתפתרו את הבעיה הבאה:
בהינתן $x$, בנו גרף קשיר לא מכוון ולא ממושקל (כלומר, משקלי כל הקשתות הם 1) כך שמתקיים $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$. כאן, $\operatorname{dis}(i, j)$ מייצג את אורך המסלול הקצר ביותר בין צומת $i$ לצומת $j$.
בעיה זו היא כמובן פשוטה מאוד... למרבה הצער, המשאבים שלכם מוגבלים, ולכן אתם מקווים למצוא גרף עם לא יותר מ-85 צמתים שעונה על הדרישות.
קלט
מקרה בדיקה יחיד מכיל מספר קבוצות נתונים.
השורה הראשונה של הקלט היא מספר קבוצות הנתונים $T$ ($1 \le T \le 2000$), המייצג את מספר קבוצות הנתונים הכלולות במקרה בדיקה זה.
עבור כל קבוצת נתונים, ישנה שורה אחת עם מספר שלם $x$ ($1 \le x \le 10^5$), המייצג את האילוץ שיש לקיים. מובטח שקיים לפחות גרף אחד עם לא יותר מ-85 צמתים המקיים את התנאי.
פלט
עבור כל קבוצת נתונים, הדפיסו בשורה הראשונה את מספר הצמתים $n$ שבו השתמשתם ($2 \le n \le 85$). לאחר מכן הדפיסו $n - 1$ שורות, כאשר השורה ה-$i$ היא מחרוזת בינארית באורך $n - i$. התו ה-$j$ בשורה ה-$i$ הוא 1 אם ורק אם קיימת קשת בין צומת $i$ לצומת $i + j$.
דוגמה
קלט
4 1 3 6 8
פלט
2 1 3 11 1 4 111 11 1 4 110 10 1