Migrated from Lutece 285 The XMM’s number

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Chinese people think of '8' as the lucky digit. XMM also likes digit 8. Moreover, XMM has his own lucky number $L$. Now she wants to construct her luckiest number which is the minimum among all positive integers that are a multiple of $L$ and consist of only digit 8.

Input

The input consists of multiple test cases. Each test case contains exactly one line containing $L(1 \leq L \leq 2,000,000,000)$.

The last test case is followed by a line containing a zero.

Output

For each test case, print a line containing the test case number( beginning with $1$) followed by a integer which is the length of XMM's luckiest number. If XMM can't construct his luckiest number, print a zero.

Samples

8
11
16
0

Case 1: 1
Case 2: 2
Case 3: 0

Note

The data used in this problem is unofficial data prepared by CyanWall. So any mistake here does not imply mistake in the offcial judge data.

Resources

2008 Asia Hefei Regional Contest Online by US