Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
76 - ZOJ 7th Anniversary Contest - A
Find 7 Faster Than John Von Neumann

Time Limit: 1 Second      Memory Limit: 32768 KB

It was said that when testing the first computer designed by von Neumann, people gave the following problem to both the legendary professor and the new computer: If the 4th digit of 2^n is 7, what is the smallest n? The machine and von Neumann began computing at the same moment, and von Neumann gave the answer first.

Now you are challenged with a similar but more complicated problem: If the K-th digit of M^n is 7, what is the smallest n?

Input

Each case is given in a line with 2 numbers: K and M (< 1,000).

Output

For each test case, please output in a line the smallest n.

You can assume:

  1. The answer always exist.
  2. The answer is no more than 100.

Sample Input

3 2
4 2
4 3

Sample Output

15
21
11


Author: CHEN, Yue
Source: ZOJ 7th Anniversary Contest
Submit    Status