WOJ1313-K尾数相等

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