Description

God Wang 是ZUFE的神犇，有一天他想到一种神奇的变换，并且将它命名为GodW变换

对于一个数字n，该变换后的值GodW(n)为，先令X=n

第一步，如果X为个位数，GodW(n)=X，否则执行第二步;

第二步，X的奇数位置的数字之和为a，偶数位置的和为b, X=a*b, 执行第一步;

现在我们有T个询问，对于每个询问输入三个整数数l,r,x

对于每个询问请输出在[l,r]这个闭区间里的数经过该变换后为x的数有多少个

Input

第一行是一个T，表示有T组询问(T<=1000)

接下来T行，每行三个整数l,r,x (0<=l<=r<=1000000)

Output

输出T行，每行一个整数，代表着答案。

Sample Input

2

1 10 2

20 25 0

Sample Output

1

2

HINT

第二个样例中满足条件的值分别为20和25

 

打表！

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std; const int Maxn=1000000+10;int L,R,X;int a[Maxn][15];int D[Maxn];int u[Maxn],tot; int F(int x){    tot=0;    int sum1=0,sum2=0;    while(x)    {        u[tot]=x%10;        x=x/10;        tot++;    }    for(int i=0;i
          
           9)  printf("0\n");            else            {                if(L!=0)                    printf("%d\n",a[R][X]-a[L-1][X]);                else                    printf("%d\n",a[R][X]);            }        }    }    return 0;}