요정 전구

어린 조니는 아주 특별한 크리스마스 선물을 받았다. 방금 뜯은 상자에는 “무한히 이어지는 요정 전구 사슬”이라고 적혀 있었다. 신이 난 소년은 새 장난감을 바닥에 펼쳤다.

조니의 사슬은 한쪽 끝만 있는 케이블이다. 어느 한 지점에서 시작하지만 반대쪽 끝은 없이 무한히 이어진다. 케이블에는 요정 전구들이 매달려 있고, 연결된 순서대로 $0$부터 시작하는 연속한 자연수 번호가 붙어 있다. 케이블은 제어판에 꽂혀 있다. 제어판에는 여러 개의 버튼이 있으며, 각 버튼은 서로 다른 색을 가지고 서로 다른 양의 정수가 적혀 있다. 버튼에 적힌 정수들은 어느 두 개를 골라도 서로소이다.

처음에는 어떤 전구도 켜져 있지 않았다. 조니는 첫 번째 버튼부터 마지막 버튼까지 하나씩 눌렀다. $i$번째 버튼을 누르면, 그 버튼에 적힌 정수 $p_i$의 배수인 번호를 가진 전구가 정확히 모두 켜지고 그 버튼의 색 $k_i$로 빛난다. 특히 이미 켜져 있던 전구라도 번호가 $p_i$의 배수라면 색이 $k_i$로 바뀐다.

따라서 각 전구의 최종 색은, 그 전구 번호를 나누어떨어지게 하는 $p_i$들 가운데 가장 나중에 눌린 버튼의 색 $k_i$가 된다.

번호가 $0, 1, \dots, r$인 전구 중 색 $k_i$로 빛나는 전구의 개수를 $L_{i,r}$라 하자. 색 $k_i$로 빛나는 전구의 비율 $C_i$는 다음과 같이 정의된다.

$C_i = \lim_{r \to \infty} \frac{L_{i,r}}{r}$

각 색 $k_i$에 대해 비율 $C_i$를 계산하여 출력하는 프로그램을 작성하라.

첫 번째 줄에 제어판의 버튼 개수 $n$ ($1 \le n \le 1{,}000$)이 주어진다. 이어지는 $n$개의 줄에는 각각 정수 $p_i$ ($1 \le p_i \le 1{,}000{,}000{,}000$)가 하나씩 주어진다. 이는 $i$번째 버튼을 누르면 $p_i$의 배수 번호를 가진 전구가 색 $k_i$로 빛남을 뜻한다. $p_i$는 조니가 버튼을 누른 순서 그대로 주어진다. $p_i$들은 어느 두 개를 골라도 서로소이다(따라서 모두 서로 다르다).

정확히 $n$개의 줄을 출력한다. $i$번째 줄에는 색 $k_i$로 빛나는 전구의 비율 $C_i$를 기약분수 $a/b$ 꼴로 출력한다. 여기서 $a$는 정수, $b$는 양의 정수이며 $a$와 $b$는 서로소이다. 만약 $C_i = 0$이면 $0/1$로 출력한다.