Nhập vào từ bàn phím hai số nguyên dương m, n (m, n <= 10¹⁶). Hãy viết chương trình in ra màn hình dạng tối giản của phân số m/n.

Ví dụ:

Mọi số nguyên dương a đều có thể viết được dưới dạng lũy thừa bậc n của số nguyên dương b (với n thuộc N^*). Chẳng hạn: 27 = 3³; 8 = 8¹. Một số nguyên dương a có thể có nhiều cách biểu diễn dưới dạng một lũy thừa, chẳng hạn: 81 = 81¹ = 9² = 3⁴.

Yêu cầu: Cho trước 3 số nguyên dương a; b; c. Gọi x là tích của 3 số a; b và c. Hỏi trong các cách viết số x thành một lũy thừa bậc n của một số nguyên dương thì số mũ n lớn nhất bằng bao nhiêu?

Dữ liệu vào: Đọc ở file văn bản LT.INP 3 số a; b; c mỗi số nằm trên một dòng (a; b; c <= 10¹²).

Dữ liệu ra: Ghi ra file văn bản LT.OUT số n thỏa mãn yêu cầu trên.

Ví dụ:

Giải thích: x = 3.3.9 = 81 = 81¹ = 9² = 3⁴. Vậy số mũ lớn nhất cần tìm là 4

Cho dãy số a₁, a₂, a₃, ... được định nghĩa như sau:

 a₁ = a₂ = 1; a_n+2 = a_n+1 + a_n với mọi n thuộc N^*.

Yêu cầu: Cho trước một số nguyên dương k (10 <= k <= 10¹⁶). Hãy tìm 2 chữ số tận cùng của số a_k trong dãy số trên.

Dữ liệu vào: File văn bản CSTC.INP chỉ có một số nguyên dương k (10 <= k <= 10¹⁶).

Dữ liệu ra: File văn bản CSTC.OUT ghi ra 2 chữ số tận cùng của số a_k trong dãy số được định nghĩa như trên.

Ví dụ:

Cho một chiếc bánh có dạng hình chữ nhật. Hãy dùng K lần cắt bánh sao cho chiếc bánh được chia thành nhiều phần nhất? Biết rằng mỗi lần cắt có thể cắt ngang hoặc dọc theo các đường thằng song song với các cạnh của chiếc bánh.

Yêu cầu: Cho số nguyên dương K. Hãy đếm số lượng phần bánh nhiều nhất có thể sau khi dùng K lần cắt bánh như trên,

Dữ liệu vào:. Cho tỏng file CUTCAKE.INP gồm:

• Dòng 1: Chứ một số nguyên K (0<= K <= 10⁹)

Dữ liệu ra: Ghi vao file CUTCAKE.OUT gồm:

• Dòng 1: Ghi ra một số nguyên là số phần bánh nhiều nhất có thể sau khi dùng K lần cắt bánh.

Example

Input

2

Output

4