Lặp hàm Phi Euler

Cho số nguyên dương $n$ được biểu diễn dưới dạng phân tích thừa số nguyên tố: $n=p_1^{a_1}·p_2^{a_2}·\dots ·p_m^{a_m}$.

Hàm phi Euler $\phi (n)$ đếm số lượng số nguyên dương không vượt quá $n$ và nguyên tố cùng nhau với $n$.

Cho số nguyên dương $k$, hãy tính ${\phi }^{(k)}(n)=\phi (\phi (\dots \phi (n)\dots ))$ (hàm $\phi$ được áp dụng $k$ lần).

Kết quả cần được biểu diễn dưới dạng phân tích thừa số nguyên tố.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $m$ - số lượng ước nguyên tố phân biệt của $n$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $p_i$ và $a_i$ - một ước nguyên tố và số mũ của nó. Các ước nguyên tố được liệt kê theo thứ tự tăng dần.
• Dòng cuối cùng chứa số nguyên $k$ - số lần áp dụng hàm $\phi$.

Dữ liệu ra

• Dòng đầu tiên in số $w$ - số lượng ước nguyên tố phân biệt của kết quả.
• $w$ dòng tiếp theo, mỗi dòng in hai số nguyên $q_i$ và $b_i$ - ước nguyên tố và số mũ của nó trong kết quả (theo thứ tự tăng dần của $q_i$, với $b_i\ge 1$).

Ràng buộc

• $1\le m\le {10}^5$
• $2\le p_i\le {10}^6$
• $1\le a_i\le {10}^{17}$
• Tổng các $a_i$ không vượt quá ${10}^{17}$
• $1\le k\le {10}^{18}$

Ví dụ

Ghi chú

Tham khảo về phân tích thừa số nguyên tố và hàm phi Euler trên Wikipedia.