수 집합 만들기

$A$부터 $B$까지의 연속한 자연수가 주어진다. Alice는 이 자연수를 몇 개의 집합으로 묶으려고 한다.

집합을 만드는 방법은 다음과 같다.

• 처음에는 자연수 하나만 들어 있는 크기 1짜리 집합을 자연수마다 만든다.
• 범위 안의 모든 자연수 쌍 $(x, y)$에 대해, $x$와 $y$에 $P$ 이상인 공통 소인수가 있으면 $x$가 속한 집합과 $y$가 속한 집합을 하나로 합친다.

예를 들어 $P = 3$, $A = 3$, $B = 15$이면 집합은 $\{3, 5, 6, 9, 10, 12, 15\}$, $\{4\}$, $\{7, 14\}$, $\{8\}$, $\{11\}$, $\{13\}$이 되고, 집합의 개수는 6이다.

$A$, $B$, $P$가 주어질 때 이 방법으로 만들어지는 집합의 개수를 구하시오.

첫 줄에 $A$, $B$, $P$가 공백을 사이에 두고 주어진다. ($1 \le A \le B \le 10^{12}$, $B \le A + 10^6$, $2 \le P \le B$)

위 규칙으로 만들어지는 집합의 개수를 출력한다.