만화경 회문

Nicholas Neverson은 Northlings Neverland Academy의 학생이다. 여느 공상에 잠긴 학생처럼, Nicholas는 수업에 집중하는 대신 어느 날 만화경을 가지고 놀고 있었다. 수학 시간이었기에 그의 공상은 곧 회문수로 이어졌다. 회문수란 앞에서 읽으나 뒤에서 읽으나 같은 수를 말한다.

그는 점심시간에 자신의 착상을 이야기한다. 여러 진법에서 동시에 회문인 수들이다. Nicholas는 그러한 수가 몇 개나 있는지 궁금해한다. 당신은 범위와 수 k가 주어졌을 때, 그 범위에서 모든 진법 j (2 ≤ j ≤ k)에 대해 회문인 수의 개수를 출력하는 프로그램을 빠르게 작성할 수 있다고 판단한다.

입력은 공백으로 구분된 세 개의 정수 a, b, k로 이루어진다. 입력은 다음 조건을 만족한다.

• 0 ≤ a ≤ b ≤ 2 000 000,
• 2 ≤ k ≤ 100 000.

a와 b 사이에 있는 수 중, 모든 진법 j (2 ≤ j ≤ k)에 대해 회문인 수의 개수를 출력한다.