Dəli qurbağa
Çoxunuz yəqin ki, Crazy Frog adlı kiçik qurbağanın macəraları haqqında mahnılar eşitmisiniz. Bu dəfə dayanmayan şirin məxluq yemək yeməyə qərar verdi, amma hətta bu sadə işi oyun şəklində yerinə yetirməyə qərar verdi. Beləliklə, N*N (N <= 50) ölçüsündə kvadrat oyun sahəsinin hər bir hüceyrəsində a_ij ağırlığında (ağırlıq təbii ədəd <= 50) bir ağcaqanad var, burada i - sıra nömrəsi, j - sütun nömrəsi. Qurbağa hüceyrədən hüceyrəyə tullanaraq ağcaqanadları yeyir. Oyunun qaydaları belədir - hər sütunda ən çox bir ağcaqanad yeyilə bilər. Hər dəfə ağcaqanad yeyildikdə, ağcaqanadın yeyildiyi sıra nömrəsini yadda saxlayırıq və oyunun sonunda ağcaqanadların yeyildiyi sıra nömrələrinin cəmi dəqiq N olmalıdır. Nəzərə alın ki, əgər bir sıra səbəbindən bir neçə ağcaqanad yeyilibsə, həmin sıra nömrəsi toplama prosesində bir neçə dəfə iştirak edir.
Verilən qaydalara riayət edərək yeyilə biləcək maksimum ağcaqanad ağırlığını müəyyən edin.
Giriş verilənləri
Girişin ilk sətiri testlərin sayını ehtiva edir. Hər testin ilk sətiri N ədədini ehtiva edir. Növbəti N sətir hər biri boşluqla ayrılmış N ədəd a(i, j) ehtiva edir.
Çıxış verilənləri
Hər test üçün çıxış faylında yeyilmiş ağcaqanadların ağırlığına bərabər olan bir ədəd çıxarılır.