题目描述

题目译自 XV OI Olimpiada Informatyczna – III etap Lampki

有一条无限长的灯链，灯泡编号为 0, 1, 2, ...，初始均熄灭。控制面板上有 $n$ 个按钮，每个按钮对应互质的正整数 $p_i$（按按下顺序排列），按下第 $i$ 个按钮时：

1. 点亮所有编号能被 $p_i$ 整除的灯泡；
2. 若这些灯泡已被点亮，颜色会更新为第 $i$ 个按钮对应的颜色 $k_i$（每个按钮颜色唯一）。

需计算每个颜色 $k_i$ 最终点亮的灯泡所占比例 $C_i = \lim_{r \to \infty} \frac{L_{i,r}}{r}$（$L_{i,r}$ 为 0~r 中颜色为 $k_i$ 的灯泡数），并以不可约分数 $a/b$ 输出。

输入格式

1. 第一行：整数 $n$（$1 \leq n \leq 1000$，按钮数量）；
2. 接下来 $n$ 行：每行一个整数 $p_i$（$1 \leq p_i \leq 10^9$，按钮对应的互质数，按按下顺序排列）。

输出格式

输出 $n$ 行，第 $i$ 行以不可约分数 $a/b$ 表示颜色 $k_i$ 的比例 $C_i$（$C_i=0$ 时输出 $0/1$）。

样例

输入

3
2
3
5

输出

4/15
4/15
1/5