A. Hotel

You are the owner of a hotel and have N rooms which have to be numbered. Unfortunately many of your customers are very superstitious. They believe that bad luck will come if their room number contains the number 13 in any way. If a number contains a 1 and anywhere after it a 3 it will bring bad luck.

A few examples:

  • 13: unlucky
  • 1253: unlucky
  • 99147344: unlucky
  • 31: good
  • 232: good
  • 879342316511: good
  

You have to buy digits and number the rooms. As you do not want to waste any money, you want to order the exact amount needed of each digit. Note that only unlucky numbers can be skipped, otherwise rooms should be numbered in order starting from 1.

Input

Each line of the input contains a single integer. Each integer is a different test case and gives N, the number of rooms in the hotel. The last line contains a 0 to mark the end of the test cases.

Output

For each given N the output should contain 10 lines describing the number of different digits needed to number N rooms.

<the number of 0s needed>
<the number of 1s needed>
<the number of 2s needed>
<the number of 3s needed>
<the number of 4s needed>
<the number of 5s needed>
<the number of 6s needed>
<the number of 7s needed>
<the number of 8s needed>
<the number of 9s needed>

Example input

20
1000
500000
0

Example output

2
12
4
1
2
2
2
2
2
2
229
312
309
270
302
300
300
300
300
300
252265
285734
354041
285734
354041
335723
262139
262078
253237
252601