A crowed of volunteers dressed in the star striped overalls have filled the starport. There starcraft leaves to the thorium mines of Haron. Their job will be hard and dangerous. Will many of them return home?

This question has an exact answer. Each of the volunteers has a ticket to the starcraft. There signed a compartment number where he is to fly. The starcraft is not passenger, it departs to Haron once a month full of the volunteers and returns back loaded with thorium. This precious metal can be loaded not in all of the compartments. In such a compartments volunteers can return home. All the others are to stay at Haron... Forever.

The compartments are numbered. The numbers of the unfit compartments (and only their numbers) are so that the digit root of the first half of the number equals to the digit root of the second half. To calculate the digit root of a number one is to summarize the digits of the number; if the result is greater or equal than 10, then the digits of the result are to be summarized again; and so on until one gets a number from 0 to 9.

How many volunteers will return home?

Even integer number N ≤ 200000 – an amount of digits used to number the compartments. There are exactly 10^N compartments numbered from 0 to 10^N-1 with the leading zeros.

The number of compartments free of thorium on the way home.