DreamGrid 有一个包含 $n$ 个点的点集 $P$。这些点被标记为 $1$ 到 $n$。 他想要在某些点对之间连接一些线段，使得最终结果构成一个三角剖分。连接点 $u$ 和 $v$ 的线段的代价为 $w_{u,v}$。 DreamGrid 想要知道最小总代价，以及能够达到该最小总代价的三角剖分方案数。 点集 $P$ 的三角剖分是三角形的集合 $\mathcal{T}$，满足：

1. $\text{conv}(P) = \bigcup_{T \in \mathcal{T}} T$，其中 $\text{conv}(P)$ 是 $P$ 的凸包。
2. $P = \bigcup_{T \in \mathcal{T}} V(T)$，其中 $V(T)$ 是三角形 $T$ 的三个顶点的集合。
3. 对于任意两个不同的三角形 $T, U \in \mathcal{T}$，$T \cap U$ 要么是一个公共顶点，要么是一条公共边，要么为空。

例如，下图展示了同一个 9 点点集的两种不同三角剖分。

来自 Wikipedia。https://en.wikipedia.org/wiki/Point_set_triangulation

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$（约 70），表示测试数据的组数。对于每组测试数据： 第一行包含一个整数 $n$ ($3 \le n \le 18$)，表示点的数量。 接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i, y_i \le 10^6$)，表示第 $i$ 个点的坐标。保证任意三点不共线。 接下来的 $n$ 行，第 $i$ 行包含 $n$ 个整数 $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}$)，表示连接线段的代价。

输出格式

对于每组测试数据，输出两个整数，分别表示最小总代价和达到该最小代价的三角剖分方案数。

样例

样例输入 1

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

样例输出 1

5 2
6 1