The MTM Machine

The MTM is one of the first digital machines ever designed. The aim of the machine is to process positive integer numbers, but due to the primitive nature of the machine only some numbers are accepted for processing; such numbers are called acceptable. When a number is accepted by MTM, the machine outputs another number, according to the rules stated below. When a number is not accepted, the machine simply outputs NOT ACCEPTABLE. A number is a non empty string of decimal digits. Given two numbers N and M, when we write NM we mean the number formed by the digits of N followed immediately by the digits of M. For example, if N is 856 and M is 112 then NM is 856112. For any number X, the associate of X is the number X2X. For example, the associate of 78 is 78278. We say that a number X produces a number Y , if number X is acceptable and when given as input to the machine MTM, the number returned by the machine is Y . The behaviour of the MTM machine is governed by the following rules: Rule 0: A number containing the digit 0 (zero) is not acceptable. Rule 1: Given any number X not containing a digit zero, then number 2X produces X. For example, 234 produces 34. Rule 2: Given any pair of numbers X, Y , if X produces Y then 3X produces the associate of Y . For example, 25 produces 5 by Rule 1, so 325 produces 525. Rule 3: No other numbers are acceptable. Your task here is to write a program that simulates the MTM machine. Input The input file contains a set of test cases. Each test case appears in a separate line, and consists of a single positive number N, N < 1032, to be processed by the MTM machine. The file ends with a line containing the number 0 that should not be processed. You may assume that the largest number output by the machine has at most 1000 digits. Output For each test case, your program should write one line with the output produced by the machine if the corresponding number is acceptable; otherwise your program should write ‘NOT ACCEPTABLE’. Sample Input 20 22 42 32 33289 0

2/2 Sample Output NOT ACCEPTABLE 2 NOT ACCEPTABLE NOT ACCEPTABLE 89289289289