Kaleidoscopic Palindromes

Time limit2sMemory limit512 MB

Summary

Count numbers in [a, b] that read as palindromes in every base from 2 through k.

Level: Medium6 of 10
Topics: Math, Implementation, Brute force, Number theory
Solved: No attempts yet

Problem

Nicholas Neverson was a student at Northlings Neverland Academy. As with any daydreaming student, Nicholas was playing around with a kaleidoscope one day instead of paying attention to the teacher. Since this was math class, his daydreams quickly turned to palindromic numbers. A palindromic number is any number which reads the same forwards and backwards.

He describes his vision to you at lunch: numbers which are palindromic in several bases at once. Nicholas wonders how many such numbers exist. You decide you can quickly code up a program that given a range and a number k, outputs the number of numbers palindromic in all bases j, 2 ≤ j ≤ k, in that range.

Input

Input consists of three space-separated integers: a, b, and k. The input satisfies the following constraints:

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

Output

Output the quantity of numbers between a and b inclusive which are palindromes in every base j, for 2 ≤ j ≤ k.

Examples2

Example 1
Input
```
1 356 2
```
Expected output
```
36
```
Example 2
Input
```
18 118 13
```
Expected output
```
0
```