Толпа добровольцев, наряженных в праздничные, звездно-полосатые робы заполнила космопорт. На глазах некоторых из этих доблестных героев, мужественных первопроходцев космоса, даже выступили слезы — наверняка, от переполнявших их сердца патриотических чувств. Еще бы — немногим выпадет такая честь! Их корабль отправится на ториевые рудники Харона, где они навсегда впишут свои имена в историю покорения Вселенной. Их работа будет трудна и полна опасностей. Многие ли из них вернутся домой?

На этот вопрос можно дать точный ответ. Каждый из добровольцев уже получил билет на корабль. В билете написан номер отсека, который займет пассажир. Космический корабль, конечно, представляет собой не комфортабельный пассажирский лайнер, а грузовое судно. Он выполняет рейсы на Харон раз в месяц — доставляет туда очередную партию добровольцев и увозит назад в своих отсеках добытый торий. К сожалению, не все отсеки подходят для перевозки драгоценного металла. В таких отсеках герои космоса, вытянувшие счастливые билеты, смогут вернуться домой на Землю. Остальным же придется остаться на Хароне. Навсегда. Впрочем, это не очень большой период времени.

Отсеки пронумерованы таким образом, что у непригодных для перевозки ториевой руды отсеков (и только у них) цифровой корень первой половины номера равен цифровому корню второй его половины. (Чтобы вычислить цифровой корень числа, его цифры складывают, если в результате получится число больше или равное 10, то цифры складывают снова и так далее, пока не получится число от 0 до 9 — это и есть цифровой корень).

Так сколько же славных добровольцев вернутся домой, чтобы сменить свои робы и ножные кандалы на сержантскую форму и электрошоковые дубинки и заняться поиском новых космических пионеров?

Единственное четное число N ≤ 200000 — количество разрядов, использованных при нумерации отсеков. На корабле ровно 10^N отсеков, пронумерованных числами от 0 до 10^N-1 с ведущими нулями.

Единственное число — количество добровольцев, отсеки которых будут свободны от руды на обратном пути.