8163번 - Lights 다국어

Little Johny has received a most unusual Christmas present. The sign on the freshly unwrapped box read "Infinite chain of fairy lights". Amused, the boy laid out his new toy on the floor.

Johny's chain is a cable with but one end: it begins at some point, but does not end anywhere. Attached to the cable are fairy lights, numbered (in order of attachment) with successive natural numbers, starting with 0. The cable itself is plugged to a control panel. There is a number of buttons on the panel, each uniquely colored and each inscribed with unique positive integer. The numbers inscribed to the buttons are pairwise relatively prime.

Upon unwrapping, no light was turned on. Thinking little at the time, Johny pressed all the buttons one by one, from first to last. To his increasing amusement he noticed that pressing the i^th button turns on exactly the lights which numbers are multiples of p_i, the number inscribed on the i^th button. Moreover, they are burning in the color k_i, the one of the button. In particular, all the lights whose numbers are multiples of p_i that were previously lit, change their color to k_i.

Johny gazes infatuated at the infinite multicolour chain and wonders what fraction of the lights burns with each particular colour. Let L_i.r denote the number of lights burning with the colour ki among the lights with numbers 0,1,…,r. Formally, the fraction C_i of the lights burning with colour ki is defined as: \( C_i= \lim_{r \to \infty} {\frac {L_{i.r}}{r}} \)

Write a programme that:

• reads the descriptions of the buttons on the control panel from the standard input,
• for each colour k_i calculates the fraction C_i, denoting the fraction of lights burning with the colour k_i,
• writes out the result to the standard output.

The first line of the standard input contains a single integer n (1  ≤ n ≤ 1,000), denoting the number of buttons on the control panel. Each of the following n lines contains a single integer p_i (1 ≤ p_i ≤ 1,000,000,000), meaning that pressing the i^th button makes the lights numbered with multiples of p_i burn with the colour k_i. The numbers p_i are given precisely in the order Johny had pressed them. The numbers p_i are pairwise relatively prime (and thus different).

Your programme should write out exactly n lines to the standard output. The i^th line should contain the fraction C_i of the lights burning with colour k_i, written as a fraction a/b, where a jest is an integer, b is a positive integer and a and b are relatively prime. If C_i=0, the fraction should be written as 0/1