Graph Hash

Time limit2sMemory limit128 MB

Summary

Given a weighted graph with up to 30 vertices, compute the LCM over all simple paths from vertex 1 to 2 of the GCD of edge weights on each path, with results up to 1000 digits.

Level: Hard8 of 10
Topics: Graph, DFS, Number theory, Backtracking
Solved: No attempts yet

Problem

A hash maps given data to a single number. For a graph, define the hash value as follows.

Consider every simple path from vertex 1 to vertex 2. The value of one path is the greatest common divisor of all edge weights on that path. The hash value of the graph is the least common multiple of the values of all such paths.

Write a program that computes this hash value for the given graph.

Input

The first line contains the number of vertices N (2 <= N <= 30).

Each of the next N lines contains N nonnegative integers, forming a symmetric adjacency matrix. A value of 0 means that there is no edge. Every nonzero edge weight is an integer from 1 to 5000.

Output

Print the graph hash value in decimal notation. The value has at most 1000 decimal digits.

Examples1

Example 1
Input
```
4
0 0 3 16
0 0 9 6
3 9 0 0
16 6 0 0
```
Expected output
```
6
```