{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eStarting with \u003ci\u003ex\u003c/i\u003e and repeatedly multiplying by \u003ci\u003ex\u003c/i\u003e, we can compute \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e with thirty multiplications:\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e × \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e3\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e3\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e, …, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e30\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e.\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003eThe operation of squaring can be appreciably shorten the sequence of multiplications. The following is a way to compute \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e with eight multiplications:\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e × \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e3\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e6\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e3\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e3\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e7\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e6\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e14\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e7\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e7\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e15\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e14\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e30\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e15\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e15\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e30\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e.\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003eThis is not the shortest sequence of multiplications to compute \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e. There are many ways with only seven multiplications. The following is one of them:\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e × \u003ci\u003ex, x\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e8\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e8\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e10\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e8\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e20\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e10\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e10\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e30\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e20\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e10\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e30\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e.\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003eIf division is also available, we can find a even shorter sequence of operations. It is possible to compute \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e with six operations (five multiplications and one division):\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e × \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e8\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e16\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e8\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e8\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e32\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e16\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e16\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e32\u003c/sup\u003e ÷ \u003ci\u003ex\u003c/i\u003e.\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003eThis is one of the most efficient ways to compute \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e if a division is as fast as a multiplication.\u003c/p\u003e\u003cp\u003eYour mission is to write a program to find the least number of operations to compute \u003ci\u003ex\u003csup\u003en\u003c/sup\u003e\u003c/i\u003e by multiplication and division starting with \u003ci\u003ex\u003c/i\u003e for the given positive integer \u003ci\u003en\u003c/i\u003e. Products and quotients appearing in the sequence should be \u003ci\u003ex\u003c/i\u003e to a positive integer’s power. In others words, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e−3\u003c/sup\u003e, for example, should never appear.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input is a sequence of one or more lines each containing a single integer \u003ci\u003en\u003c/i\u003e. \u003ci\u003en\u003c/i\u003e is positive and less than or equal to 1000. The end of the input is indicated by a zero.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eYour program should print the least total number of multiplications and divisions required to compute \u003ci\u003ex\u003csup\u003en\u003c/sup\u003e\u003c/i\u003e starting with \u003ci\u003ex\u003c/i\u003e for the integer \u003ci\u003en\u003c/i\u003e. The numbers should be written each in a separate line without any superfluous characters such as leading or trailing spaces.\u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n31\r\n70\r\n91\r\n473\r\n512\r\n811\r\n953\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n6\r\n8\r\n9\r\n11\r\n9\r\n13\r\n12\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}