"Let's go!", thought a hotel's manager entering an elevator. He pressed the tenth floor button and meditated. The day was not easy. The manager looked at the floor indicator, saw the number 9, and prepared to get out. But the elevator did not stop. The nine gave place to eight, then to seven. The manager became amazed. He remembered precisely that he had entered the elevator at the first floor. He was sure that the elevator goes up. Yes, it was not an easy day, but not to such an extent! Then he saw eight instead of seven, then there was nine again, then ten, and the elevator stopped.
The strange behavior of the elevator worried the manager. The next morning he decided that the problem was with the floor indicator, and so a repairman should be called for.
The repairman comes by a helicopter, enters the building through a window at one of the floors, gets into the elevator, and goes several floors up or down comparing the numbers on the indicator with the numbers of floors. The indicator can show several digits, and each digit place has 7 short linear indicating lamps shown here:
These lamps allow to show any digit:
The indicator does not show leading zeros and has no "extra" lamps, that is lamps which will never light up in this building. A properly working lamp switches on or off when it is needed; a defective lamp is always on or always off. During his journey in the elevator, the repairman must find all the defective lamps. For the sake of economy, it is necessary to minimize the number of passages between floors needed for this work. The floors are numbered with successive integers starting with 1.
The only line contains the number of floors in the building N (4 < N < 101000).
You should output the minimal number of passages between adjacent floors that the repairman should go in the elevator in order to find all the defective lamps.
Problem Author: Idea Leonid Volkov, prepared by Pavel Egorov, Igor Goldberg
Problem Source: VIII Collegiate Students Urals Programming Contest. Yekaterinburg, March 11-16, 2004