Line Graph L(G) can be considered as an operator on an undirected graph G just like Complementary Graph and Dual Graph.

Rikka generalizes Line Graph to edge-weighted undirected graphs. For a graph , L(G) is still an edge-weighted undirected graph which is constructed in the following way:
1. L(G) has |E| vertices and the ith vertex corresponds to the ith edge in G.
2. There is an edge between i,j in L(G) if and only if edge i and j have at least one common vertices in G. And the edge weight is equal to the sum of the weights of edge i and j in G.

For example, in the following picture, the right graph is the line graph of the left one. Vertex 1,2,3,4 in L(G) correspond to edge (1,2),(1,4),(1,3),(3,4) in G. And if all edges in the left graph have weight 1, the edges in the right graph will have weight 2.


Now, Rikka has an edge-weighted undirected complete graph G with n vertices. And she constructs a graph G'=L(G). It is clear that G' is connected.

Let d(i,j) be the length of the shortest path between vertex i,j in G'(the length of each edge is equal to its weight), K be the number of vertices in G', Rikka wants you to calculate .

The first line contains a single number t(1 ≤ t ≤ 3), the number of the testcases.

For each testcase, the first line contains one single integer n(2 ≤ n ≤ 500). 

Then n lines follow, each line contains n integers wi,j(0 ≤ wi,j ≤ 109), the weight of each edge in G. Since there are no self circles in G, the value of wi,i is meaningless.

The input guarantees that for all 1 ≤ i ≠ j ≤ n, wi,i=0 and wi,j = wj,i.

For each testcase, output a single line with a single number, the answer modulo 998244353.

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

0
6
56