시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 22 5 5 25.000%

문제

해시(hash)란 주어진 데이터를 하나의 수로 표현하는 것을 말한다. 예를 들어서 "1024"와 같은 문자열을 1024 라는 수로 생각하는 방법은 해시의 한 예이다. 또, 영단어에서 'a'부터 'z'까지를 1에서 26까지의 수로 생각하여 그 수들을 합한 것도 해시의 한 예이다. 이런 해시를 적용하면 "ab"와 같은 영단어는 3이라는 수가 되고, "ace"와 같은 영단어는 9라는 수가 된다.

당신은 그래프에 대해서 해시 함수를 하나 설계하였다. 당신이 설계한 해시 값은 그래프의 1번 정점에서 2번 정점까지 가는 모든 경로들의 경로 값의 최소공배수로 정의한다. 경로 값은 경로 상에 있는 모든 간선의 가중치들의 최대공약수로 정의한다. 물론 경로에서는 같은 정점이 두 번 이상 나와서는 안 된다.

예를 들어 위와 같은 그래프를 보자. 위의 그래프에서 1번 정점에서 2번 정점까지 가는 경로는 1-4-2, 1-3-2의 두 개가 있다. 각 경로의 경로 값은 2(16, 6의 최대공약수), 3(3, 9의 최대공약수)이 되고, 따라서 해시 값은 6(2, 3의 최소공배수)이 된다.

하나의 그래프가 주어졌을 때, 그 그래프의 해시 값(위에서 설계한 해시 함수를 이용하여 계산한)을 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 그래프의 정점의 개수 N(2≤N≤30)이 주어진다. 다음 N개의 줄에는 N개의 음 아닌 정수로 대칭적인 인접 행렬이 주어진다. 0인 경우는 간선이 없을 때를 나타내며, 그 외의 간선의 가중치는 1이상 5,000이하의 자연수이다.

출력

첫째 줄에 해시 값을 출력한다. 이 값은 10진수로 1000자리를 넘지 않는다.

예제 입력

4
0 0 3 16
0 0 9 6
3 9 0 0
16 6 0 0

예제 출력

6

힌트