#include <stdio.h>

int main(void)
{
int i, j, k, times[10] = {0}, num[10], flg, cnt = 0;

for(i=0; i<10; i++) num[i] = i;

for(i=1; i<=100000000; i++) {
for(j=i; j; j/=10) times[j%10]++;
for(j=9,flg=0; j>0; j--) {
for(k=0; k<j; k++) {
if((times[num[k]] > times[num[k+1]]) ||
(times[num[k]] == times[num[k+1]] && num[k] > num[k+1])) {
int temp = num[k];
num[k] = num[k+1];
num[k+1] = temp;
flg = 1;
}
}
}
if(flg) cnt++;
if(i%1000 == 0) printf("%d:%d\n", i, cnt);
}

return 0;
}