Chinese people think of "\textbf{8}" as the lucky digit. Bob also likes digit "\textbf{8}". Moreover, Bob has his own lucky number \textit{\textbf{L}}. Now he wants to construct his luckiest number which is the minimum among all positive integers that are a multiple of \textit{\textbf{L}} and consist of only digit "\textbf{8}". \InputFile The input consists of multiple test cases. Each test case contains exactly one line containing \textit{\textbf{L}}\textit{ }(\textbf{1} ≤ \textit{\textbf{L}} ≤ \textbf{2000000000}). The last test case is followed by a line containing a zero. \OutputFile For each test case, print a line containing the test case number( beginning with \textbf{1}) followed by a integer which is the length of Bob's luckiest number. If Bob can't construct his luckiest number, print a zero.