Белгілі болғандай, APSP (барлық жұптар арасындағы ең қысқа жолдар) есебі min+ матрицаларды көбейтумен тығыз байланысты. Бүгін біз сізге келесі есепті шығаруды ұсынамыз:
Берілген $x$ саны бойынша $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$ шартын қанағаттандыратын бағытталмаған салмақсыз байланысқан граф (яғни барлық қырлардың салмағы 1-ге тең) құрастырыңыз. Мұндағы $\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$ болатын екілік жол болып табылады. $i$-ші жолдың $j$-ші таңбасы тек $i$ төбесі мен $i + j$ төбесінің арасында қыр болған жағдайда ғана 1-ге тең болады.
Мысал
Кіріс деректер
4 1 3 6 8
Шығыс деректер
2 1 3 11 1 4 111 11 1 4 110 10 1