题目描述

农夫John想从正整数A~B之间选一些质数来作为奶牛的编号，作为编号的数各位上的数字至少有一个特定的数字D。如A为11、B为15，D为3时，则A~B之间有11、13两个质数，但组成11的两个数字中没有3，所有只有一个数13符合条件。

输入格式

一行三个正整数A,B,D，之间用空格隔开。

输出格式

一行一个正整数，表示包含数字D的质数个数。

10 15 3

1

提示

对于100%的数据满足：

1≤A≤B≤4×${10}^6$，B≤A+2×${10}^6$，0≤D≤9。