【题目描述】

话说高考研讨会上有许多志愿者，其中有许多女生，性格开朗、活泼的 zn 很快就与这 些女生打成一片，把 z 同学晾在了一边。现场人很多，小 z 一转眼发现找不到了 zn 一伙人 了，肿么办，计划赶不上变化啊，小 z 找到了志愿者总管：一个带着小红帽的家伙，小红帽说了：想知道她在哪啊，听说你是 410 的，听说 410 都是些牛逼人啊，我得考考你。

 小红帽出题了，咱们现在处于 1 区域，zn 处于 2 区域，一共有n个区域，有一些路连接着两个区域，路有长度，小红帽规定一条从 1 到 2 的路径的权值为这条路上每条路长度的最大公约数，他叫你求出所有能从 区域 1 到 2 的路径的权值的最小公倍数(路径上的点最多经过一次) 。

【输入格式】

第一行：n

接下来是一个 n*n 的矩阵，i行j列的值代表从 i区域到 j区域的路径长度，若不连通，则为 0 

【输出格式】

所求的最小公倍数 

【样例输入】

4

0 0 3 16

0 0 9 6

3 9 0 0

16 6 0 0

【样例输出】

6

【提示】

2≤n≤25

1<路径的权值<2000

Hint：不用高精度哦

【来源】

在此键入。