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  of triangles, such that 

    1. ,where  conv(P) is the convex hull of P.
     2.. ,where V(T) is the set of three vertices of triangle T.

For every distinct pair   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.

输入描述:

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 ≤ n ≤ 18)-- the number of points.

Each of the next n  lines contains two integers xi and yi (0 ≤ xi,yi ≤ 106) , 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  integers wi,1,wi,2,...wi,n (0 ≤ wi,j ≤ 106,wi,i = 0,  wi, j = wj,i) , indicating the cost for drawing segments.

输出描述:

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

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

5 2
6 1