Triangulation

DreamGrid has a point set \(P\) of \(n\) points. The points are labeled from \(1\) to \(n\).

He would like to draw some segments between some pairs of points such that the final result forms a triangulation. The cost for drawing segment between points \(u\) and \(v\) is \(w_{u,v}\).

DreamGrid would like to know the minimum total cost and the number of triangulations which can achieve the minimum total cost.

A triangulation of a point set \(P\) is a collection \(\mathcal{T}\) of triangles, such that

• \(\text{conv}(P) = \bigcup\limits_{T \in \mathcal{T}}T\), where \(\text{conv}(P)\) is the convex hull of \(P\).
• \(P = \bigcup\limits_{T \in \mathcal{T}}V(T)\), where \(V(T)\) is the set of three vertices of triangle \(T\).
• For every distinct pair \(T, U \in \mathcal{T}\), \(T \cap U\) is either a common vertex, or a common edge, or empty.

For example, the following are two different triangulations of the same set of 9 points.

Input

There are multiple test cases. The first line of input contains an integer \(T\) (about 70), indicating the number of test cases. For each test case:

The first line contains an integer \(n\) \((3 \le n \le 18)\) -- the number of points.

Each of the next \(n\) lines contains two integers \(x_i\) and \(y_i\) \((0 \le x_i, y_i \le 10^6)\), denoting the coordinates of the \(i\)-th point. No three points lie on the same line.

The \(i\)-th of the next \(n\) lines contains \(n\) integers \(w_{i,1}, w_{i,2}, \dots, w_{i,n}\) (\(0 \le w_{i, j} \le 10^6, w_{i,i}=0, w_{i,j}=w_{j,i}\)), indicating the cost for drawing segments.

Output

For each test case, output two integers denoting the minimum cost and the number of triangulations.

Sample Input

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

Sample Output

5 2
6 1