Cho một cái cây có một cái gốc và mỗi nút cha có \(K\) nút con. Gọi \(f(d)\) là số lượng nút có khoảng cách đến gốc bằng \(d\).

Yêu cầu: Cho trước hai số nguyên dương \(N,P\). Tìm số \(D\) nhỏ nhất thoả mãn \(f(D)≡N\) (mod P). Nếu không tìm được số \(D\) nào thoả mãn, in ra \(−1\)

Input

• Đề bài có nhiều testcase, mỗi testcase gồm \(3\) số nguyên \(K,P,N\)(\(1 \leq K,P,N \leq 10^9\))

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \leq K \leq 20\), \(1 \leq N,P \leq 50\).
• Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

2 6 4
2 2 4

2
-1