시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 43 15 12 30.769%

문제

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 ≤ 1012, B ≤ A + 106, 2 ≤ P ≤ B)

출력

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

예제 입력 1

3 15 3

예제 출력 1

6

예제 입력 2

10 20 5

예제 출력 2

9

예제 입력 3

10 20 3

예제 출력 3

7