Krallıqlar

Bir neçə krallıq ciddi maliyyə çətinlikləri ilə üzləşib. İllər boyu onlar bir-birindən getdikcə daha çox pul borc alıblar. İndi, onların öhdəlikləri ifşa edildikdə, iflas qaçılmazdır...

n krallıq mövcuddur. Hər bir krallıq cütü (A, B) üçün A krallığının B krallığına qaytarmalı olduğu qızıl miqdarı d[AB] tam ədədi ilə ifadə olunur (biz güman edirik ki, d[BA] = -d[AB]). Əgər krallığın mənfi balansı varsa (alacağından daha çox ödəməli olduğu), o, müflis ola bilər. Müflislik bütün öhdəlikləri, həm müsbət, həm də mənfi, aradan qaldırır, sanki krallıq mövcudluğunu dayandırmış kimi. Sonra növbəti krallıq müflis ola bilər və s., qalan bütün krallıqlar maliyyə baxımından sabit olana qədər.

Kim birinci düşərsə, fərqli ssenarilər yarana bilər. Xüsusilə, bəzən yalnız bir krallıq qala bilər. Hər bir krallıq üçün müəyyən edin ki, o, yeganə sağ qalan ola bilərmi.

Giriş Məlumatları

Birinci sətir testlərin sayı t-ni ehtiva edir. Testlərin təsvirləri aşağıda verilmişdir:

Hər bir testin təsviri n krallığın sayını ehtiva edən sətirlə başlayır (1 ≤ n ≤ 20). Sonra n sətir gəlir, hər biri n ədəd ehtiva edir. i-ci sətirdəki j-ci ədəd i-ci krallığın j-ci krallığa qaytarmalı olduğu d[ij] qızıl sikkələrin sayıdır. d[ii] = 0 və d[ij] = -d[ji] hər bir 1 ≤ i, j ≤ n üçün olduğunu qəbul edə bilərsiniz. Həmçinin, bütün mümkün i, j üçün |d[ij]| ≤ 10^6-dır.

Çıxış Məlumatları

Hər bir test üçün yeganə sağ qalan ola biləcək krallıqların indekslərini artan sırada ehtiva edən bir sətir çıxarın. Əgər belə krallıqlar yoxdursa, bir ədəd 0 çıxarın.