Ở Đất nước Ba Lan xinh đẹp, có nàng công chúa tới tuổi kén chồng. Nhà vua muốn tìm ra một chàng rể thông minh kiệt xuất xứng đáng với công chúa nên đã đề ra cuộc thi: Thử tài nhanh trí. Nội dung của cuộc thi là chàng hoàng tử nào nhanh chóng đưa ra kết quả bài toán của nhà vua trong thời gian tối đa 1s sẽ được gặp mặt công chúa. Là một nhà lập trình tài ba, bạn hãy giúp các chàng hoàng tử nhé. Bài toán như sau:

Cho số tự nhiên N (N ≥2), ta có thể phân tích N thành tích các thừa số nguyên tố với dạng N=~~P1^(x1 ~)~×P2^(x2~ )×…×~Pk^(xk~ )~, trong đó P1<P2<⋯<Pk là các số nguyên tố và x1,x2,…,xk>0. Gọi S là tổng các số mũ xi có giá trị chẵn và P là tổng các số mũ xj có giá trị lẻ. Chú ý là S + P =x1+x2+⋯+xk.

Yêu cầu: Hãy đưa ra giá trị của S và P.

Dữ liệu cho trong file văn bản BAI4.INP gồm một số tự nhiên N (2 ≤N).

Kết quả ghi ra file văn bản BAI4.OUT gồm hai dòng:

Dòng thứ nhất ghi giá trị của S.

Dòng thứ hai ghi giá trị của P.

Ví dụ:

BAI4.INP

20

Bai4.out

2

1

Giải thích:

20 = ~2^2×5^1~

S = 2; P = 1

Giới hạn:

Có 30% số test ứng với N ≤10^6, P1<P2<⋯<Pk<20 trong đó N=P~1^(x1 )×P~2^(x2~ )×…×Pk^(xk ~);

Có 30% số test ứng với N ≤1~0^6~;

Có 40% số test ứng với N ≤~10^12~.