EIU Programming Practices and Exams

Tú và Đạt là 2 sinh viên IT có tiềm năng tuy nhiên khá là nghiện game. Mỗi ngày 2 người này đều bỏ ra khá nhiều thời gian và tiền bạc để đi chơi net. Một hôm 2 anh em bị Phú và Duy phát hiện trốn học đi chơi game, lại còn dẫn bạn gái theo mà không rủ mình, quá tức giận Phú và Duy méc cho mẹ của Tú và Đạt.

Mẹ của Tú và Đạt rất tức giận khi phát hiện con mình ham chơi, ngay lúc đang nấu củ cải, cô ấy yêu cầu 2 anh em phải nấu xong mới được ra ngoài, Tú và Đạt đã lỡ hẹn với bạn gái nên không thể không đi và đành phải cầu xin mẹ tha thứ. Người mẹ đồng ý với điều kiện phải đưa ra được đáp số mà cô yêu cầu. Cô nói: "Có N củ cải và mỗi lần chỉ được lấy 1 nửa số củ cải cho vào nồi, nếu không thể chia đôi do lẻ 1 củ thì cho luôn củ thừa đó vào nồi. Tú tính số lần lẻ 1 củ cho vào nổi, Đạt số lần không lẻ. Ví dụ mẹ có 5 củ, lần đầu cho vào 2 củ và 1 củ lẻ, còn 2 củ, lần 2 cho vào 1 củ thì không lẻ củ nào, còn 1, lần cuối cho vào 1 củ, củ này là lẻ, hết, vậy Tú là 2, Đạt là 1".

Thời gian gấp lắm rồi! Phải nhanh lên thôi!

Input

Số nguyên N không âm, không lớn hơn 10^9, là số củ cải mẹ có.

Output

Một dòng gồm 2 số nguyên lần lượt là đáp số chính xác của Tú và Đạt.

Example

Input:
5

Output:
2 1