从键盘输入一个自然数K(K>1),若存在自然数M和N(M>N),使得K^M和K^N均大于或等于1000、且它们的末尾三位数相等，则称M和N是一对?K尾相等数?。请编写程序，输出M+N值最小的K尾相等数。 

输入格式

输入数据有多组，以0结束。

输出格式

对于每个输入，输出一行。

样例输入

2
0

样例输出

120

#include<stdio.h>
#include<math.h>
int mantissa(int k,int m,int n){
    int tm,i,sum[1000];
    for(i=0;i<1000;i++)
    sum[i]=-1;
    while((int)pow(k,m)<1000)
       m++;
    tm=(int)pow(k,m)%1000;
    sum[tm]=m;
    for(i=m+1;i<1000;i++)//数组的下标为对应的尾数，内容为指数 
    {
        tm=tm*(k%1000)%1000;
        if(sum[tm]!=-1) 
        	return i+sum[tm];
        else
           	sum[tm]=i;
	}
}
int main(){
    int k;
    while(scanf("%d",&k)!=EOF){
    	if(k==0)
        break;
        printf("%d\n",mantissa(k,1,1));
    }
    return 0;
}