АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Давид-д N тооны сав мөн N төрлийн бөмбөг байгаа.

Бөмбөгнүүд саванд холилдон орсон байгаа ба Давид аль нэг саванд ижил төрлийн л бөмбөг байлгахыг хүсч байгаа.

Жишээлбэл

N=2 сав мөн 2 төрлийн бөмбөг байгаа. Савыг ч тэр бөмбөгний төрлийг ч тэр 0-с N-1 хүртэл дугаарлан 

N*N хэмжээтэй M матрицад тэмдэглэнэ. Үүний дагуу  М[сав][бөмбөгний төрөл]

Давид 2 өөр саванд байгаа 1, 1 бөмбөгийг харгалзан сольж чадна. ( Доорхын дагуу )

Хэрэв Давид өөрийн хүсч байгаагаар бөмбөгүүдийг ялгаж аль нэг саванд ижил өнгийн бөмбөг байрлуулж

чадах бол “Possible” гэж хэвлэ.  Харин чадахгүй бол “Impossible” гэж хэвлэ.

Оролт

Эхний мөрөнд тестийн тоо t өгөгдөнө. 1 <= t <= 10.

Тест бүр шинэ мөрөнд өгөгдсөн N мөн N*N хэмжээний M матриц өгөгдөнө.

1 <= N <= 100,  0 <= M[сав][бөмбөгний төрөл] <= 10^9.

Гаралт

Тест бүрийн хариуг шинэ мөрөнд хэвлэнэ.

Жишээ

Оролт 1

2

2

1 1

1 1

2

0 2

1 1

Гаралт 1

Possible

Impossible

Оролт 2

2

3
2 1 2
3 3 3
3
0 2 1
1 1 1
2 0 0

1 3 1

Гаралт 2

 Impossible

Possible

Орчуулсан : Дархан-Уул аймгийн Монгол-Оюу сургуулийн 11.1 ангийн сурагч Э.Цэлмэг