Smallest third number for a given lcm

Find the smallest positive integer c with lcm(a, b, c) equal to L, or output -1 when none exists.

Medium4Number theoryMathInterviewNo attempts yetTime limit1sMemory limit256 MB

Problem

You are given three integers aa, bb, and LL. Find the smallest positive integer cc such that lcm(a,b,c)=L\operatorname{lcm}(a, b, c) = L, where lcm(a,b,c)\operatorname{lcm}(a, b, c) is the least common multiple of aa, bb, and cc.

Input

The first line contains aa, bb, and LL, separated by spaces. (1a,b1061 \le a, b \le 10^6, 1L10121 \le L \le 10^{12})

Output

Print the smallest cc that satisfies the condition. If no such cc exists, print 1-1.