Giải bài trực tuyến

Bé Johnny nhận được một món quà Giáng sinh kỳ lạ. Trên hộp quà còn chưa bóc có hàng chữ: “Dàn đèn màu cổ tích dài vô hạn”. Thích thú, cậu bé đặt món đồ chơi lên nền nhà.

Dàn đèn của Johnny là một sợi dây cáp nhưng chỉ có một đầu: nó bắt đầu tại một điểm nhưng không có điểm kết thúc. Gắn vào sợi dây cáp là các ngọn đèn cổ tích, đánh số (theo thứ tự được gắn) bằng các số tự nhiên liên tiếp, bắt đầu từ 0. Bản thân sợi dây cáp được gắn vào một bảng điều khiển. Có một số nút bấm trên bảng điều khiển, mỗi nút được sơn một màu riêng biệt và được gán cho một số hiệu riêng biệt là số nguyên dương. Các số hiệu của các nút đôi một nguyên tố cùng nhau.

Khi mở gói quà ra, chưa có ngọn đèn nào được bật. Suy nghĩ một lát, Johnny bấm lần lượt các nút, từ đầu đến cuối. Cậu bé càng lúc càng thích thú khi phát hiện ra rằng bấm nút thứ i sẽ bật các bóng đèn có số hiệu là bội số của p_i, số hiệu của nút thứ i. Hơn nữa, chúng sáng lên với màu k_i, là màu của nút bấm đó. Đặc biệt, tất cả các bóng đèn có số hiệu là bội số của p_i mà đã được chiếu sáng trước đó sẽ chuyển thành màu k_i.

Johnny ngắm dàn đèn muôn vàn màu sắc và tự hỏi tỉ lệ phần đèn sáng của mỗi màu là bao nhiêu. Gọi L_i,r là số bóng đèn sáng với màu k_i trong số các ngọn đèn có số hiệu 0,1,...,r. Tỉ lệ C_i phần bóng đèn sáng với màu k_i được định nghĩa bằng:

Yêu cầu

Viết chương trình đọc mô tả của các nút trên bảng điều khiển và với mỗi màu k_i tính giá trị C_i là phân số mô tả tỉ lệ phần bóng đèn sáng với màu k_i.

Dữ liệu

Dòng đầu tiên chứa một số nguyên duy nhất n (1 ≤ n ≤ 1000), mô tả số nút trên bảng điều khiển. Mỗi trong số n dòng sau chứa một số nguyên duy nhất p_i (1 ≤ p_i ≤ 10⁹), cho biết rằng bấm nút thứ i sẽ làm các bóng đèn có số hiệu là bội số của p_i sáng lên với màu k_i. Các số p_i được cho theo thứ tự mà Johnny đã bấm. Các số p_i đôi một nguyên tố cùng nhau (và do đó phân biệt).

Kết quả

Chương trình phải in ra đúng n dòng. Dòng thứ i chứa phân số C_i là tỉ lệ phần bóng đèn sáng với màu k_i, viết dưới dạng a/b, với a là một số nguyên, b là số nguyên dương và a, b nguyên tố cùng nhau. Nếu C_i=0, phân số phải được viết dưới dạng 0/1.

Ví dụ

Dữ liệu
3
2
3
5

Kết quả
4/15
4/15
1/5