Lũy thừa một phép toán hai ngôi của toán học thực hiện trên hai số a và b, kết quả của phép toán lũy thừa là tích số của phép nhân : có b thừa số a nhân với nhau. Lũy thừa ký hiệu là a^b, đọc là lũy thừa bậc b của a, số a gọi là cơ số, số b gọi là số mũ.

Trong toán học, nếu số nguyên a chia hết cho số nguyên b thì số b được gọi là ước của số nguyên a, a được gọi là bội của b. Số nguyên dương u lớn nhất là ước của cả hai số nguyên a, b được gọi là ước số chung lớn nhất (ƯCLN) của a và b.

Trong bài tập này bạn được giao 3 số nguyên \(A, B\) và \(N\). Bạn cần viết chương trình tìm ước chung lớn nhất của \(A^N\) và \(B\). Hay GCD(\(A^N\), \(B\)).

Input

• Chứa 3 số nguyên \(A, B, N (1 ≤ A, B, N ≤ 10^9)\)

Output

• Một dòng duy nhất là GCD thu được.

Example

2 3 3

1

2 4 5

4