순환의 아름다움

베이스 $k$ 실수의 소수 부분이 순수 순환 소수이면, 이 실수를 아름답다(beautiful)고 한다.

10진수 정수 $n$, $m$이 주어진다. $1 \leq x \leq n$, $1 \leq y \leq m$을 만족하는 정수 $x$, $y$에 대해 $\frac{x}{y}$로 나타낼 수 있는 순수 순환 실수 중 값이 서로 다른 수의 개수를 구하라.

실수가 다음 형태로 쓸 수 있으면 순수 순환 소수이다. $\displaystyle a.\dot{c\_1} c\_2 c\_3 \ldots c\_{p-1} \dot{c\_p}$ 여기서 $a$는 베이스 $k$ 정수이고, $p \geq 1$이며, 각 $1 \leq i \leq p$에 대해 $c\_i$는 베이스 $k$ 숫자이다.

예를 들어 10진법에서 $0.45454545\cdots = 0.\dot{4}\dot{5}$는 순수 순환 소수이고, $\frac{5}{11}$ 또는 $\frac{10}{22}$로 나타낼 수 있다. 10진법에서 $0.166666\cdots = 0.1\dot{6}$은 순수 순환 소수가 아니지만, $\frac{1}{6}$ 같은 분수로 나타낼 수 있다.

주의: 정수는 순수 순환 소수이다. 소수 부분을 0의 반복이나 $k-1$의 반복으로 쓸 수 있기 때문이다. 소수 부분이 0이 아닌 유한 소수는 순수 순환 소수가 아니다.

중국에서는 순환 부분을 점 한두 개로 표시한다. 일부 국가에서는 순환 부분 위에 선을 그어 표시한다.

한 줄에 세 정수 $n$, $m$, $k$가 주어진다. 각 값의 의미는 문제 설명과 같다.

모든 조건을 만족하는 아름다운 수의 개수를 한 줄에 출력한다.

모든 테스트 케이스에 대해 $1 \leq n \leq 10^9$, $1 \leq m \leq 10^9$, $2 \leq k \leq 2000$이다.