34971번 - 괴물이 되고 싶어

이번 기말고사 시험을 망친 규서는 괴물이 되어 세계를 엉망진창으로 만들 계획을 세우고 있다.

세계는 총 $Q$개의 도시로 이루어져 있고, 규서는 이들을 모두 파괴할 계획이다. 각 도시는 $N \times N$의 격자 모양이며 $i$행 $j$열에는 높이가 $2^{A_{ij}}$인 건물이 존재한다. $A_{ij}$는 $0$부터 $N^2 - 1$까지의 정수 중 하나로, 중복되는 값은 존재하지 않는다.

규서는 파괴광선을 원하는 만큼 순차적으로 사용하여 건물을 파괴할 수 있다. 파괴광선은 임의의 열이나 행에 사용 가능하다.

• 파괴광선을 하나의 행에 사용하게 되면, 해당 행에 있는 모든 건물의 높이가 해당 행의 건물 중 최소 높이만큼 낮아진다.
• 파괴광선을 하나의 열에 사용하게 되면, 해당 열에 있는 모든 건물의 높이가 해당 열의 건물 중 최소 높이만큼 낮아진다.

예를 들어, 건물이 $3$개이고 각각의 높이가 $2$, $4$, $8$인 행에 파괴광선을 사용하면 높이가 $2$씩 줄어들어 각각 $0$, $2$, $6$이 된다.

각 도시에 대해 파괴광선을 적절히 사용하여 남길 수 있는 건물 높이 합의 최솟값을 $998 \,244\,353$으로 나눈 나머지를 구하여라.

첫 번째 줄에 도시의 수 $Q$가 주어진다. ($1 \leq Q \leq 1 \, 000$)

각 도시에 대한 정보는 $N+1$개의 줄로 이루어져 있다. ($1 \leq N \leq 1 \, 000$)

도시에 대한 정보의 첫 번째 줄에 도시의 크기 $N$이 주어진다. 두 번째 줄부터 $N$개의 줄에 걸쳐 정수 $N$개가 공백으로 구분되어 주어진다. $i$번째 줄의 $j$번째 수는 $A_{ij}$로 도시의 $i$행 $j$열에 존재하는 건물의 높이가 $2^{A_{ij}}$임을 의미한다.

$Q$개의 도시에 대해 $N$의 합은 $1 \, 000$을 넘지 않는다.

첫 번째 줄부터 $Q$개의 줄에 걸쳐 각 도시에 대해 파괴광선을 적절히 사용하여 남길 수 있는 건물 높이 합의 최솟값을 $998 \,244\,353$으로 나눈 나머지를 한 줄에 하나씩 출력하라.