Камоме қазіргі уақытта салмақталған бағытталмаған графтардағы үшбұрышты жолдарды зерттеп жүр. Нақтырақ айтқанда, жол үшбұрышты деп аталады, егер және тек егер:

• Бұл жолдың ұзындығы $2$-ден аспаса, немесе
• Осы жолдағы кез келген үш түрлі $e_1$, $e_2$ және $e_3$ қырлары үшін $w(e_1)$, $w(e_2)$ және $w(e_3)$ әрқашан үшбұрыштың үш қабырғасын құрай алса.

Оң бүтін $x$, $y$ және $z$ сандары тек $x < y + z$, $y < z + x$ және $z < x + y$ болғанда ғана үшбұрыштың қабырғаларын құрай алатынын еске түсіріңіз.

Камоме сізге салмақталған бағытталмаған граф берді. Сізге әрбір $(u, v)$ нүктелер жұбы үшін $u$-дан басталып, $v$-да аяқталатын үшбұрышты жолдың бар-жоғын анықтау керек. Әрбір төбеден өзіне әрқашан үшбұрышты жол бар деп есептейміз.

Кіріс деректер

Әрбір тест бірнеше тест жиынтығынан тұрады. Бірінші жолда тест жиынтықтарының санын білдіретін бір бүтін сан $t$ ($1 \le t \le 10^5$) берілген. Одан кейін тест жиынтықтарының сипаттамасы беріледі.

Бірінші жолда осы графтың төбелер мен қырлар санын білдіретін екі бүтін сан $n, m$ ($1 \le n, m \le 3000$, $1 \le \sum n^2, \sum m^2 \le 3000^2$) берілген.

Келесі $m$ жолдың әрқайсысында салмағы $w_i$ болатын $(u_i, v_i)$ қырын білдіретін үш бүтін сан $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$) берілген.

Граф байланыспаған болуы мүмкін немесе онда ілмектер (self-loop) не еселі қырлар (multiple edges) болуы мүмкін.

Шығыс деректер

Әрбір тест жиынтығы үшін $n$ жол шығарыңыз, әр жол $n$ таңбадан тұратын жол болуы керек, мұндағы $j$-ші таңба $s_{i,j}$: егер $i$-ден басталып $j$-де аяқталатын үшбұрышты жол болмаса 0, әйтпесе 1.

Мысалдар

Кіріс 1

2
4 3
1 2 2
2 3 2
3 4 3
8 7
1 2 3
2 3 4
3 4 1
3 5 2
2 6 2
6 7 4
6 8 5

Шығыс 1

1111
1111
1111
1111
11101110
11111111
11111111
01111000
11111000
11100111
11100111
01100111