$题目描述$

$Georgia$ 和 $Bob$ 现在在一个海盗的洞穴里。经过探查，他们发现洞内有很多房间，这些房间都通过一些道路连接在一起。有两种房间：一种是装满珠宝的房间，只有一条路相连（我们称这种房间为珠宝房），另一种是空的，但至少有两条路相连。在这个洞穴中，所有的房间都像一棵树一样连接起来。

现在他们在一个珠宝室里，他们想一个一个地去所有的珠宝室拿所有的珠宝，然后回到他们现在住的房间。当然，他们希望步行最短的距离来实现这个目标。经过探索，他们已经绘制了洞穴的整个地图，现在地图就在鲍勃的手中。但 $Bob$ 不想把地图给 $Georgia$，因为 $Georgia$ 总是想展示她有多聪明。$Bob$ 只是告诉 $Georgia$ 任意两个珠宝室之间的最小距离，并要求 $Georgia$ 告诉他访问所有珠宝室以达到最小距离的顺序。如果订单不是唯一的，$Georgia$ 应该告诉 $Bob$ 可能的不同订单的总数。

虽然 $Georgia$ 是一个非常明确的女孩，但她认为她很难完全靠自己解决这个问题。你能帮助她吗？

$输入$

有 $multiply$ 测试用例。在每个测试用例的第一行中，有一个整数 $N$（$2 <= N <= 30$），它表示珠宝房间的数量（这些房间的编号从 $1$ 到 $N$）。然后是 $N$ 行，每行包含 $N$ 个不大于 $100$ 的非负整数。第 $j$ 行中的第 $i$ 个整数表示房间 $i$ 和房间 $j$ 之间的距离。很明显，房间 $i$ 和房间 $i$ 之间的距离为 $0$，房间 $i$ 和房间 $j$ 之间的距离是一个正整数，等于房间 $j$ 和房间 $i$ 之间的距离。

您可以假设 $Georgia$ 和 $Bob$ 最初在房间 $1$ 中。

$N = 0$ 的大小写表示输入结束，不应处理此行。

$输出$

对于每个测试用例，在一行中输出两个整数。这两个整数由单个空格分隔。第一个数字是他们应该走的最短距离，才能拿到所有的珠宝，然后再回去。第二个数字是访问所有珠宝室以实现上述目的的不同订单的数量。

不同订单的数量可能非常大，因此如果此值不小于 $2005$，则应将此值除以 $2005$，然后只输出余数值。

$输入数据$ $1$

3  
0 3 4  
3 0 5  
4 5 0  
0

$输出数据$ $1$

12 2

$来源$

$北京$ $2005$ 预选赛