Given integers ~a, n, p~, find the smallest nonnegative integer ~x~ such that ~a^x \equiv n \pmod p~.

Constraints

~1 < a, n, p < 2^{31}~

~p~ is a prime number.

Input Specification

The only line contains three space-separated integers, ~a~, ~n~, and ~p~.

Output Specification

Output the smallest possible nonnegative integer ~x~; if no such ~x~ exists, output DNE.

Sample Input 1

7 4 5

Sample Output 1

2

Sample Input 2

10 7 11

Sample Output 2

DNE