LeetCode Improvisation Technique

The solution to this problem required a little improvisation technique, which some might say it is "cheating" but that's very subjective.
The problem is this one, take a look: https://leetcode.com/problems/2-keys-keyboard/description/

Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
2. Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.

Example 1:

Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

The solution I came up with was a breadth-first-search (BFS) where the transitions (copy or paste) are the enqueueing steps. So far so good, but unfortunately the code timed out towards the very last steps. Here is the improvisation though: the input asked was from 1..1000. Now that's tiny. What I could do then was using the BFS code (which actually runs relatively fast) pre-compute all answers from 1..1000, create a hashtable with all the answers, and simply index the hashtable. Hence, the first solution, although workable, did not make the cut, whereas the second one did. Both solutions below. Cheers, Marcelo.

Solution 1 (BFS, times out, but works):

public class Solution
{
public int MinSteps(int n)
{
Queue queue = new Queue();
Hashtable alreadySeen = new Hashtable();

EnqueueItem ei = new EnqueueItem("A", "", 0, null);
alreadySeen.Add(ei.current + "@" + ei.paste, true);
queue.Enqueue(ei);
while (queue.Count > 0)
{
EnqueueItem currentItem = (EnqueueItem)queue.Dequeue();

if (currentItem.current.Length == n)
{
//PrintBacktrack(currentItem);
return currentItem.numberSteps;
}

//Copy
if (currentItem.current.Length <= n && currentItem.paste.Length > 0 && !alreadySeen.ContainsKey(currentItem.current + currentItem.paste + "@" + currentItem.paste))
{
EnqueueItem currentItemCopy = new EnqueueItem(currentItem.current + currentItem.paste, currentItem.paste, currentItem.numberSteps + 1, currentItem);
alreadySeen.Add(currentItem.current + currentItem.paste + "@" + currentItem.paste, true);
queue.Enqueue(currentItemCopy);
}

//Paste
if (currentItem.current.Length <= n && !alreadySeen.ContainsKey(currentItem.current + "@" + currentItem.current))
{
EnqueueItem currentItemPaste = new EnqueueItem(currentItem.current, currentItem.current, currentItem.numberSteps + 1, currentItem);
alreadySeen.Add(currentItem.current + "@" + currentItem.current, true);
queue.Enqueue(currentItemPaste);
}
}

return -1;
}

private void PrintBacktrack(EnqueueItem ei)
{
if (ei.from != null) PrintBacktrack(ei.from);
if (ei.from == null) return;
if (ei.current == ei.paste) Console.WriteLine("Step {0}: pasted '{1}' to the clipboard. Current: {2}. Clipboard = {3}", ei.numberSteps, ei.current, ei.current, ei.paste);
else Console.WriteLine("Step {0}: copied '{1}' from the clipboard. Current: {2}. Clipboard = {3}", ei.numberSteps, ei.paste, ei.current, ei.paste);
}

private class EnqueueItem
{
public string current = "";
public string paste = "";
public int numberSteps = 0;
public EnqueueItem from = null;

public EnqueueItem(string current,
   string paste,
   int numberSteps,
   EnqueueItem from)
{
this.current = current;
this.paste = paste;
this.numberSteps = numberSteps;
if (from != null)
{
this.from = new EnqueueItem(from.current, from.paste, from.numberSteps, from.from);
}
}
}
}

Solution 2 (indexation based on solution 1, works fast):

public class Solution {
private Hashtable ht = null;

public Solution()
{
ht = new Hashtable();

ht.Add(1, 0);
ht.Add(2, 2);
ht.Add(3, 3);
ht.Add(4, 4);
ht.Add(5, 5);
ht.Add(6, 5);
ht.Add(7, 7);
ht.Add(8, 6);
ht.Add(9, 6);
ht.Add(10, 7);
ht.Add(11, 11);
ht.Add(12, 7);
ht.Add(13, 13);
ht.Add(14, 9);
ht.Add(15, 8);
ht.Add(16, 8);
ht.Add(17, 17);
ht.Add(18, 8);
ht.Add(19, 19);
ht.Add(20, 9);
ht.Add(21, 10);
ht.Add(22, 13);
ht.Add(23, 23);
ht.Add(24, 9);
ht.Add(25, 10);
ht.Add(26, 15);
ht.Add(27, 9);
ht.Add(28, 11);
ht.Add(29, 29);
ht.Add(30, 10);
ht.Add(31, 31);
ht.Add(32, 10);
ht.Add(33, 14);
ht.Add(34, 19);
ht.Add(35, 12);
ht.Add(36, 10);
ht.Add(37, 37);
ht.Add(38, 21);
ht.Add(39, 16);
ht.Add(40, 11);
ht.Add(41, 41);
ht.Add(42, 12);
ht.Add(43, 43);
ht.Add(44, 15);
ht.Add(45, 11);
ht.Add(46, 25);
ht.Add(47, 47);
ht.Add(48, 11);
ht.Add(49, 14);
ht.Add(50, 12);
ht.Add(51, 20);
ht.Add(52, 17);
ht.Add(53, 53);
ht.Add(54, 11);
ht.Add(55, 16);
ht.Add(56, 13);
ht.Add(57, 22);
ht.Add(58, 31);
ht.Add(59, 59);
ht.Add(60, 12);
ht.Add(61, 61);
ht.Add(62, 33);
ht.Add(63, 13);
ht.Add(64, 12);
ht.Add(65, 18);
ht.Add(66, 16);
ht.Add(67, 67);
ht.Add(68, 21);
ht.Add(69, 26);
ht.Add(70, 14);
ht.Add(71, 71);
ht.Add(72, 12);
ht.Add(73, 73);
ht.Add(74, 39);
ht.Add(75, 13);
ht.Add(76, 23);
ht.Add(77, 18);
ht.Add(78, 18);
ht.Add(79, 79);
ht.Add(80, 13);
ht.Add(81, 12);
ht.Add(82, 43);
ht.Add(83, 83);
ht.Add(84, 14);
ht.Add(85, 22);
ht.Add(86, 45);
ht.Add(87, 32);
ht.Add(88, 17);
ht.Add(89, 89);
ht.Add(90, 13);
ht.Add(91, 20);
ht.Add(92, 27);
ht.Add(93, 34);
ht.Add(94, 49);
ht.Add(95, 24);
ht.Add(96, 13);
ht.Add(97, 97);
ht.Add(98, 16);
ht.Add(99, 17);
ht.Add(100, 14);
ht.Add(101, 101);
ht.Add(102, 22);
ht.Add(103, 103);
ht.Add(104, 19);
ht.Add(105, 15);
ht.Add(106, 55);
ht.Add(107, 107);
ht.Add(108, 13);
ht.Add(109, 109);
ht.Add(110, 18);
ht.Add(111, 40);
ht.Add(112, 15);
ht.Add(113, 113);
ht.Add(114, 24);
ht.Add(115, 28);
ht.Add(116, 33);
ht.Add(117, 19);
ht.Add(118, 61);
ht.Add(119, 24);
ht.Add(120, 14);
ht.Add(121, 22);
ht.Add(122, 63);
ht.Add(123, 44);
ht.Add(124, 35);
ht.Add(125, 15);
ht.Add(126, 15);
ht.Add(127, 127);
ht.Add(128, 14);
ht.Add(129, 46);
ht.Add(130, 20);
ht.Add(131, 131);
ht.Add(132, 18);
ht.Add(133, 26);
ht.Add(134, 69);
ht.Add(135, 14);
ht.Add(136, 23);
ht.Add(137, 137);
ht.Add(138, 28);
ht.Add(139, 139);
ht.Add(140, 16);
ht.Add(141, 50);
ht.Add(142, 73);
ht.Add(143, 24);
ht.Add(144, 14);
ht.Add(145, 34);
ht.Add(146, 75);
ht.Add(147, 17);
ht.Add(148, 41);
ht.Add(149, 149);
ht.Add(150, 15);
ht.Add(151, 151);
ht.Add(152, 25);
ht.Add(153, 23);
ht.Add(154, 20);
ht.Add(155, 36);
ht.Add(156, 20);
ht.Add(157, 157);
ht.Add(158, 81);
ht.Add(159, 56);
ht.Add(160, 15);
ht.Add(161, 30);
ht.Add(162, 14);
ht.Add(163, 163);
ht.Add(164, 45);
ht.Add(165, 19);
ht.Add(166, 85);
ht.Add(167, 167);
ht.Add(168, 16);
ht.Add(169, 26);
ht.Add(170, 24);
ht.Add(171, 25);
ht.Add(172, 47);
ht.Add(173, 173);
ht.Add(174, 34);
ht.Add(175, 17);
ht.Add(176, 19);
ht.Add(177, 62);
ht.Add(178, 91);
ht.Add(179, 179);
ht.Add(180, 15);
ht.Add(181, 181);
ht.Add(182, 22);
ht.Add(183, 64);
ht.Add(184, 29);
ht.Add(185, 42);
ht.Add(186, 36);
ht.Add(187, 28);
ht.Add(188, 51);
ht.Add(189, 16);
ht.Add(190, 26);
ht.Add(191, 191);
ht.Add(192, 15);
ht.Add(193, 193);
ht.Add(194, 99);
ht.Add(195, 21);
ht.Add(196, 18);
ht.Add(197, 197);
ht.Add(198, 19);
ht.Add(199, 199);
ht.Add(200, 16);
ht.Add(201, 70);
ht.Add(202, 103);
ht.Add(203, 36);
ht.Add(204, 24);
ht.Add(205, 46);
ht.Add(206, 105);
ht.Add(207, 29);
ht.Add(208, 21);
ht.Add(209, 30);
ht.Add(210, 17);
ht.Add(211, 211);
ht.Add(212, 57);
ht.Add(213, 74);
ht.Add(214, 109);
ht.Add(215, 48);
ht.Add(216, 15);
ht.Add(217, 38);
ht.Add(218, 111);
ht.Add(219, 76);
ht.Add(220, 20);
ht.Add(221, 30);
ht.Add(222, 42);
ht.Add(223, 223);
ht.Add(224, 17);
ht.Add(225, 16);
ht.Add(226, 115);
ht.Add(227, 227);
ht.Add(228, 26);
ht.Add(229, 229);
ht.Add(230, 30);
ht.Add(231, 21);
ht.Add(232, 35);
ht.Add(233, 233);
ht.Add(234, 21);
ht.Add(235, 52);
ht.Add(236, 63);
ht.Add(237, 82);
ht.Add(238, 26);
ht.Add(239, 239);
ht.Add(240, 16);
ht.Add(241, 241);
ht.Add(242, 24);
ht.Add(243, 15);
ht.Add(244, 65);
ht.Add(245, 19);
ht.Add(246, 46);
ht.Add(247, 32);
ht.Add(248, 37);
ht.Add(249, 86);
ht.Add(250, 17);
ht.Add(251, 251);
ht.Add(252, 17);
ht.Add(253, 34);
ht.Add(254, 129);
ht.Add(255, 25);
ht.Add(256, 16);
ht.Add(257, 257);
ht.Add(258, 48);
ht.Add(259, 44);
ht.Add(260, 22);
ht.Add(261, 35);
ht.Add(262, 133);
ht.Add(263, 263);
ht.Add(264, 20);
ht.Add(265, 58);
ht.Add(266, 28);
ht.Add(267, 92);
ht.Add(268, 71);
ht.Add(269, 269);
ht.Add(270, 16);
ht.Add(271, 271);
ht.Add(272, 25);
ht.Add(273, 23);
ht.Add(274, 139);
ht.Add(275, 21);
ht.Add(276, 30);
ht.Add(277, 277);
ht.Add(278, 141);
ht.Add(279, 37);
ht.Add(280, 18);
ht.Add(281, 281);
ht.Add(282, 52);
ht.Add(283, 283);
ht.Add(284, 75);
ht.Add(285, 27);
ht.Add(286, 26);
ht.Add(287, 48);
ht.Add(288, 16);
ht.Add(289, 34);
ht.Add(290, 36);
ht.Add(291, 100);
ht.Add(292, 77);
ht.Add(293, 293);
ht.Add(294, 19);
ht.Add(295, 64);
ht.Add(296, 43);
ht.Add(297, 20);
ht.Add(298, 151);
ht.Add(299, 36);
ht.Add(300, 17);
ht.Add(301, 50);
ht.Add(302, 153);
ht.Add(303, 104);
ht.Add(304, 27);
ht.Add(305, 66);
ht.Add(306, 25);
ht.Add(307, 307);
ht.Add(308, 22);
ht.Add(309, 106);
ht.Add(310, 38);
ht.Add(311, 311);
ht.Add(312, 22);
ht.Add(313, 313);
ht.Add(314, 159);
ht.Add(315, 18);
ht.Add(316, 83);
ht.Add(317, 317);
ht.Add(318, 58);
ht.Add(319, 40);
ht.Add(320, 17);
ht.Add(321, 110);
ht.Add(322, 32);
ht.Add(323, 36);
ht.Add(324, 16);
ht.Add(325, 23);
ht.Add(326, 165);
ht.Add(327, 112);
ht.Add(328, 47);
ht.Add(329, 54);
ht.Add(330, 21);
ht.Add(331, 331);
ht.Add(332, 87);
ht.Add(333, 43);
ht.Add(334, 169);
ht.Add(335, 72);
ht.Add(336, 18);
ht.Add(337, 337);
ht.Add(338, 28);
ht.Add(339, 116);
ht.Add(340, 26);
ht.Add(341, 42);
ht.Add(342, 27);
ht.Add(343, 21);
ht.Add(344, 49);
ht.Add(345, 31);
ht.Add(346, 175);
ht.Add(347, 347);
ht.Add(348, 36);
ht.Add(349, 349);
ht.Add(350, 19);
ht.Add(351, 22);
ht.Add(352, 21);
ht.Add(353, 353);
ht.Add(354, 64);
ht.Add(355, 76);
ht.Add(356, 93);
ht.Add(357, 27);
ht.Add(358, 181);
ht.Add(359, 359);
ht.Add(360, 17);
ht.Add(361, 38);
ht.Add(362, 183);
ht.Add(363, 25);
ht.Add(364, 24);
ht.Add(365, 78);
ht.Add(366, 66);
ht.Add(367, 367);
ht.Add(368, 31);
ht.Add(369, 47);
ht.Add(370, 44);
ht.Add(371, 60);
ht.Add(372, 38);
ht.Add(373, 373);
ht.Add(374, 30);
ht.Add(375, 18);
ht.Add(376, 53);
ht.Add(377, 42);
ht.Add(378, 18);
ht.Add(379, 379);
ht.Add(380, 28);
ht.Add(381, 130);
ht.Add(382, 193);
ht.Add(383, 383);
ht.Add(384, 17);
ht.Add(385, 23);
ht.Add(386, 195);
ht.Add(387, 49);
ht.Add(388, 101);
ht.Add(389, 389);
ht.Add(390, 23);
ht.Add(391, 40);
ht.Add(392, 20);
ht.Add(393, 134);
ht.Add(394, 199);
ht.Add(395, 84);
ht.Add(396, 21);
ht.Add(397, 397);
ht.Add(398, 201);
ht.Add(399, 29);
ht.Add(400, 18);
ht.Add(401, 401);
ht.Add(402, 72);
ht.Add(403, 44);
ht.Add(404, 105);
ht.Add(405, 17);
ht.Add(406, 38);
ht.Add(407, 48);
ht.Add(408, 26);
ht.Add(409, 409);
ht.Add(410, 48);
ht.Add(411, 140);
ht.Add(412, 107);
ht.Add(413, 66);
ht.Add(414, 31);
ht.Add(415, 88);
ht.Add(416, 23);
ht.Add(417, 142);
ht.Add(418, 32);
ht.Add(419, 419);
ht.Add(420, 19);
ht.Add(421, 421);
ht.Add(422, 213);
ht.Add(423, 53);
ht.Add(424, 59);
ht.Add(425, 27);
ht.Add(426, 76);
ht.Add(427, 68);
ht.Add(428, 111);
ht.Add(429, 27);
ht.Add(430, 50);
ht.Add(431, 431);
ht.Add(432, 17);
ht.Add(433, 433);
ht.Add(434, 40);
ht.Add(435, 37);
ht.Add(436, 113);
ht.Add(437, 42);
ht.Add(438, 78);
ht.Add(439, 439);
ht.Add(440, 22);
ht.Add(441, 20);
ht.Add(442, 32);
ht.Add(443, 443);
ht.Add(444, 44);
ht.Add(445, 94);
ht.Add(446, 225);
ht.Add(447, 152);
ht.Add(448, 19);
ht.Add(449, 449);
ht.Add(450, 18);
ht.Add(451, 52);
ht.Add(452, 117);
ht.Add(453, 154);
ht.Add(454, 229);
ht.Add(455, 25);
ht.Add(456, 28);
ht.Add(457, 457);
ht.Add(458, 231);
ht.Add(459, 26);
ht.Add(460, 32);
ht.Add(461, 461);
ht.Add(462, 23);
ht.Add(463, 463);
ht.Add(464, 37);
ht.Add(465, 39);
ht.Add(466, 235);
ht.Add(467, 467);
ht.Add(468, 23);
ht.Add(469, 74);
ht.Add(470, 54);
ht.Add(471, 160);
ht.Add(472, 65);
ht.Add(473, 54);
ht.Add(474, 84);
ht.Add(475, 29);
ht.Add(476, 28);
ht.Add(477, 59);
ht.Add(478, 241);
ht.Add(479, 479);
ht.Add(480, 18);
ht.Add(481, 50);
ht.Add(482, 243);
ht.Add(483, 33);
ht.Add(484, 26);
ht.Add(485, 102);
ht.Add(486, 17);
ht.Add(487, 487);
ht.Add(488, 67);
ht.Add(489, 166);
ht.Add(490, 21);
ht.Add(491, 491);
ht.Add(492, 48);
ht.Add(493, 46);
ht.Add(494, 34);
ht.Add(495, 22);
ht.Add(496, 39);
ht.Add(497, 78);
ht.Add(498, 88);
ht.Add(499, 499);
ht.Add(500, 19);
ht.Add(501, 170);
ht.Add(502, 253);
ht.Add(503, 503);
ht.Add(504, 19);
ht.Add(505, 106);
ht.Add(506, 36);
ht.Add(507, 29);
ht.Add(508, 131);
ht.Add(509, 509);
ht.Add(510, 27);
ht.Add(511, 80);
ht.Add(512, 18);
ht.Add(513, 28);
ht.Add(514, 259);
ht.Add(515, 108);
ht.Add(516, 50);
ht.Add(517, 58);
ht.Add(518, 46);
ht.Add(519, 176);
ht.Add(520, 24);
ht.Add(521, 521);
ht.Add(522, 37);
ht.Add(523, 523);
ht.Add(524, 135);
ht.Add(525, 20);
ht.Add(526, 265);
ht.Add(527, 48);
ht.Add(528, 22);
ht.Add(529, 46);
ht.Add(530, 60);
ht.Add(531, 65);
ht.Add(532, 30);
ht.Add(533, 54);
ht.Add(534, 94);
ht.Add(535, 112);
ht.Add(536, 73);
ht.Add(537, 182);
ht.Add(538, 271);
ht.Add(539, 25);
ht.Add(540, 18);
ht.Add(541, 541);
ht.Add(542, 273);
ht.Add(543, 184);
ht.Add(544, 27);
ht.Add(545, 114);
ht.Add(546, 25);
ht.Add(547, 547);
ht.Add(548, 141);
ht.Add(549, 67);
ht.Add(550, 23);
ht.Add(551, 48);
ht.Add(552, 32);
ht.Add(553, 86);
ht.Add(554, 279);
ht.Add(555, 45);
ht.Add(556, 143);
ht.Add(557, 557);
ht.Add(558, 39);
ht.Add(559, 56);
ht.Add(560, 20);
ht.Add(561, 31);
ht.Add(562, 283);
ht.Add(563, 563);
ht.Add(564, 54);
ht.Add(565, 118);
ht.Add(566, 285);
ht.Add(567, 19);
ht.Add(568, 77);
ht.Add(569, 569);
ht.Add(570, 29);
ht.Add(571, 571);
ht.Add(572, 28);
ht.Add(573, 194);
ht.Add(574, 50);
ht.Add(575, 33);
ht.Add(576, 18);
ht.Add(577, 577);
ht.Add(578, 36);
ht.Add(579, 196);
ht.Add(580, 38);
ht.Add(581, 90);
ht.Add(582, 102);
ht.Add(583, 64);
ht.Add(584, 79);
ht.Add(585, 24);
ht.Add(586, 295);
ht.Add(587, 587);
ht.Add(588, 21);
ht.Add(589, 50);
ht.Add(590, 66);
ht.Add(591, 200);
ht.Add(592, 45);
ht.Add(593, 593);
ht.Add(594, 22);
ht.Add(595, 29);
ht.Add(596, 153);
ht.Add(597, 202);
ht.Add(598, 38);
ht.Add(599, 599);
ht.Add(600, 19);
ht.Add(601, 601);
ht.Add(602, 52);
ht.Add(603, 73);
ht.Add(604, 155);
ht.Add(605, 27);
ht.Add(606, 106);
ht.Add(607, 607);
ht.Add(608, 29);
ht.Add(609, 39);
ht.Add(610, 68);
ht.Add(611, 60);
ht.Add(612, 27);
ht.Add(613, 613);
ht.Add(614, 309);
ht.Add(615, 49);
ht.Add(616, 24);
ht.Add(617, 617);
ht.Add(618, 108);
ht.Add(619, 619);
ht.Add(620, 40);
ht.Add(621, 32);
ht.Add(622, 313);
ht.Add(623, 96);
ht.Add(624, 24);
ht.Add(625, 20);
ht.Add(626, 315);
ht.Add(627, 33);
ht.Add(628, 161);
ht.Add(629, 54);
ht.Add(630, 20);
ht.Add(631, 631);
ht.Add(632, 85);
ht.Add(633, 214);
ht.Add(634, 319);
ht.Add(635, 132);
ht.Add(636, 60);
ht.Add(637, 27);
ht.Add(638, 42);
ht.Add(639, 77);
ht.Add(640, 19);
ht.Add(641, 641);
ht.Add(642, 112);
ht.Add(643, 643);
ht.Add(644, 34);
ht.Add(645, 51);
ht.Add(646, 38);
ht.Add(647, 647);
ht.Add(648, 18);
ht.Add(649, 70);
ht.Add(650, 25);
ht.Add(651, 41);
ht.Add(652, 167);
ht.Add(653, 653);
ht.Add(654, 114);
ht.Add(655, 136);
ht.Add(656, 49);
ht.Add(657, 79);
ht.Add(658, 56);
ht.Add(659, 659);
ht.Add(660, 23);
ht.Add(661, 661);
ht.Add(662, 333);
ht.Add(663, 33);
ht.Add(664, 89);
ht.Add(665, 31);
ht.Add(666, 45);
ht.Add(667, 52);
ht.Add(668, 171);
ht.Add(669, 226);
ht.Add(670, 74);
ht.Add(671, 72);
ht.Add(672, 20);
ht.Add(673, 673);
ht.Add(674, 339);
ht.Add(675, 19);
ht.Add(676, 30);
ht.Add(677, 677);
ht.Add(678, 118);
ht.Add(679, 104);
ht.Add(680, 28);
ht.Add(681, 230);
ht.Add(682, 44);
ht.Add(683, 683);
ht.Add(684, 29);
ht.Add(685, 142);
ht.Add(686, 23);
ht.Add(687, 232);
ht.Add(688, 51);
ht.Add(689, 66);
ht.Add(690, 33);
ht.Add(691, 691);
ht.Add(692, 177);
ht.Add(693, 24);
ht.Add(694, 349);
ht.Add(695, 144);
ht.Add(696, 38);
ht.Add(697, 58);
ht.Add(698, 351);
ht.Add(699, 236);
ht.Add(700, 21);
ht.Add(701, 701);
ht.Add(702, 24);
ht.Add(703, 56);
ht.Add(704, 23);
ht.Add(705, 55);
ht.Add(706, 355);
ht.Add(707, 108);
ht.Add(708, 66);
ht.Add(709, 709);
ht.Add(710, 78);
ht.Add(711, 85);
ht.Add(712, 95);
ht.Add(713, 54);
ht.Add(714, 29);
ht.Add(715, 29);
ht.Add(716, 183);
ht.Add(717, 242);
ht.Add(718, 361);
ht.Add(719, 719);
ht.Add(720, 19);
ht.Add(721, 110);
ht.Add(722, 40);
ht.Add(723, 244);
ht.Add(724, 185);
ht.Add(725, 39);
ht.Add(726, 27);
ht.Add(727, 727);
ht.Add(728, 26);
ht.Add(729, 18);
ht.Add(730, 80);
ht.Add(731, 60);
ht.Add(732, 68);
ht.Add(733, 733);
ht.Add(734, 369);
ht.Add(735, 22);
ht.Add(736, 33);
ht.Add(737, 78);
ht.Add(738, 49);
ht.Add(739, 739);
ht.Add(740, 46);
ht.Add(741, 35);
ht.Add(742, 62);
ht.Add(743, 743);
ht.Add(744, 40);
ht.Add(745, 154);
ht.Add(746, 375);
ht.Add(747, 89);
ht.Add(748, 32);
ht.Add(749, 114);
ht.Add(750, 20);
ht.Add(751, 751);
ht.Add(752, 55);
ht.Add(753, 254);
ht.Add(754, 44);
ht.Add(755, 156);
ht.Add(756, 20);
ht.Add(757, 757);
ht.Add(758, 381);
ht.Add(759, 37);
ht.Add(760, 30);
ht.Add(761, 761);
ht.Add(762, 132);
ht.Add(763, 116);
ht.Add(764, 195);
ht.Add(765, 28);
ht.Add(766, 385);
ht.Add(767, 72);
ht.Add(768, 19);
ht.Add(769, 769);
ht.Add(770, 25);
ht.Add(771, 260);
ht.Add(772, 197);
ht.Add(773, 773);
ht.Add(774, 51);
ht.Add(775, 41);
ht.Add(776, 103);
ht.Add(777, 47);
ht.Add(778, 391);
ht.Add(779, 60);
ht.Add(780, 25);
ht.Add(781, 82);
ht.Add(782, 42);
ht.Add(783, 38);
ht.Add(784, 22);
ht.Add(785, 162);
ht.Add(786, 136);
ht.Add(787, 787);
ht.Add(788, 201);
ht.Add(789, 266);
ht.Add(790, 86);
ht.Add(791, 120);
ht.Add(792, 23);
ht.Add(793, 74);
ht.Add(794, 399);
ht.Add(795, 61);
ht.Add(796, 203);
ht.Add(797, 797);
ht.Add(798, 31);
ht.Add(799, 64);
ht.Add(800, 20);
ht.Add(801, 95);
ht.Add(802, 403);
ht.Add(803, 84);
ht.Add(804, 74);
ht.Add(805, 35);
ht.Add(806, 46);
ht.Add(807, 272);
ht.Add(808, 107);
ht.Add(809, 809);
ht.Add(810, 19);
ht.Add(811, 811);
ht.Add(812, 40);
ht.Add(813, 274);
ht.Add(814, 50);
ht.Add(815, 168);
ht.Add(816, 28);
ht.Add(817, 62);
ht.Add(818, 411);
ht.Add(819, 26);
ht.Add(820, 50);
ht.Add(821, 821);
ht.Add(822, 142);
ht.Add(823, 823);
ht.Add(824, 109);
ht.Add(825, 24);
ht.Add(826, 68);
ht.Add(827, 827);
ht.Add(828, 33);
ht.Add(829, 829);
ht.Add(830, 90);
ht.Add(831, 280);
ht.Add(832, 25);
ht.Add(833, 31);
ht.Add(834, 144);
ht.Add(835, 172);
ht.Add(836, 34);
ht.Add(837, 40);
ht.Add(838, 421);
ht.Add(839, 839);
ht.Add(840, 21);
ht.Add(841, 58);
ht.Add(842, 423);
ht.Add(843, 284);
ht.Add(844, 215);
ht.Add(845, 31);
ht.Add(846, 55);
ht.Add(847, 29);
ht.Add(848, 61);
ht.Add(849, 286);
ht.Add(850, 29);
ht.Add(851, 60);
ht.Add(852, 78);
ht.Add(853, 853);
ht.Add(854, 70);
ht.Add(855, 30);
ht.Add(856, 113);
ht.Add(857, 857);
ht.Add(858, 29);
ht.Add(859, 859);
ht.Add(860, 52);
ht.Add(861, 51);
ht.Add(862, 433);
ht.Add(863, 863);
ht.Add(864, 19);
ht.Add(865, 178);
ht.Add(866, 435);
ht.Add(867, 37);
ht.Add(868, 42);
ht.Add(869, 90);
ht.Add(870, 39);
ht.Add(871, 80);
ht.Add(872, 115);
ht.Add(873, 103);
ht.Add(874, 44);
ht.Add(875, 22);
ht.Add(876, 80);
ht.Add(877, 877);
ht.Add(878, 441);
ht.Add(879, 296);
ht.Add(880, 24);
ht.Add(881, 881);
ht.Add(882, 22);
ht.Add(883, 883);
ht.Add(884, 34);
ht.Add(885, 67);
ht.Add(886, 445);
ht.Add(887, 887);
ht.Add(888, 46);
ht.Add(889, 134);
ht.Add(890, 96);
ht.Add(891, 23);
ht.Add(892, 227);
ht.Add(893, 66);
ht.Add(894, 154);
ht.Add(895, 184);
ht.Add(896, 21);
ht.Add(897, 39);
ht.Add(898, 451);
ht.Add(899, 60);
ht.Add(900, 20);
ht.Add(901, 70);
ht.Add(902, 54);
ht.Add(903, 53);
ht.Add(904, 119);
ht.Add(905, 186);
ht.Add(906, 156);
ht.Add(907, 907);
ht.Add(908, 231);
ht.Add(909, 107);
ht.Add(910, 27);
ht.Add(911, 911);
ht.Add(912, 30);
ht.Add(913, 94);
ht.Add(914, 459);
ht.Add(915, 69);
ht.Add(916, 233);
ht.Add(917, 138);
ht.Add(918, 28);
ht.Add(919, 919);
ht.Add(920, 34);
ht.Add(921, 310);
ht.Add(922, 463);
ht.Add(923, 84);
ht.Add(924, 25);
ht.Add(925, 47);
ht.Add(926, 465);
ht.Add(927, 109);
ht.Add(928, 39);
ht.Add(929, 929);
ht.Add(930, 41);
ht.Add(931, 33);
ht.Add(932, 237);
ht.Add(933, 314);
ht.Add(934, 469);
ht.Add(935, 33);
ht.Add(936, 25);
ht.Add(937, 937);
ht.Add(938, 76);
ht.Add(939, 316);
ht.Add(940, 56);
ht.Add(941, 941);
ht.Add(942, 162);
ht.Add(943, 64);
ht.Add(944, 67);
ht.Add(945, 21);
ht.Add(946, 56);
ht.Add(947, 947);
ht.Add(948, 86);
ht.Add(949, 86);
ht.Add(950, 31);
ht.Add(951, 320);
ht.Add(952, 30);
ht.Add(953, 953);
ht.Add(954, 61);
ht.Add(955, 196);
ht.Add(956, 243);
ht.Add(957, 43);
ht.Add(958, 481);
ht.Add(959, 144);
ht.Add(960, 20);
ht.Add(961, 62);
ht.Add(962, 52);
ht.Add(963, 113);
ht.Add(964, 245);
ht.Add(965, 198);
ht.Add(966, 35);
ht.Add(967, 967);
ht.Add(968, 28);
ht.Add(969, 39);
ht.Add(970, 104);
ht.Add(971, 971);
ht.Add(972, 19);
ht.Add(973, 146);
ht.Add(974, 489);
ht.Add(975, 26);
ht.Add(976, 69);
ht.Add(977, 977);
ht.Add(978, 168);
ht.Add(979, 100);
ht.Add(980, 23);
ht.Add(981, 115);
ht.Add(982, 493);
ht.Add(983, 983);
ht.Add(984, 50);
ht.Add(985, 202);
ht.Add(986, 48);
ht.Add(987, 57);
ht.Add(988, 36);
ht.Add(989, 66);
ht.Add(990, 24);
ht.Add(991, 991);
ht.Add(992, 41);
ht.Add(993, 334);
ht.Add(994, 80);
ht.Add(995, 204);
ht.Add(996, 90);
ht.Add(997, 997);
ht.Add(998, 501);
ht.Add(999, 46);
ht.Add(1000, 21);
}
public int MinSteps(int n)
{
return (int)ht[n];
}
}