12901번 - Number Sets

문제

A~B까지의 연속한 자연수들이 주어진다. Alice는 이 자연수들을 몇 개의 집합으로 묶고 싶어한다.

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

• 처음 시작할 때는 각 자연수가 들어있는 크기 1짜리 집합들을 만든다.
• 범위 내에 있는 모든 자연수 쌍 (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 ≤ A ≤ B ≤ 10¹², B ≤ A + 10⁶, 2 ≤ P ≤ B)

출력

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

제한

힌트