Cho số nguyên dương \(a,b,d\). Mỗi bước bạn được thực hiện một trong hai phép biến đổi sau:

1. Nhân \(a\) với \(k\), trong đó \(1<k \le d\);
2. Chia \(a\) cho \(k\), trong đó \(1<k \le d\) và \(a\) chia hết cho \(k\);

Yêu cầu: Tìm số phép biến đổi ít nhất để đưa \(a\) thành \(b\).

Input

• Gồm một dòng chứa ba số nguyên dương \(a,b,d\);

Output

• Gồm một dòng chứa một số là số phép biến đổi ít nhất cần thực hiện. Nếu không biến đổi được ghi \(-1\).

Scoring

• Subtask \(1\): \(a,b,d \le 10\);
• Subtask \(2\): \(a,b,d \le 10^9\);

Example

3 5 6

2

3 1 2

-1