Here are the records from a busy telephone system with one million users:
The telephone number of the caller and the called number in record are and where come from the "Lagged Fibonacci Generator":
If = then the user is assumed to have misdialled and the call fails; otherwise the call is successful.
From the start of the records, we say that any pair of users and are friends if calls or vice-versa. Similarly, is a friend of a friend of if is a friend of and is a friend of ; and so on for longer chains.
The Prime Minister's phone number is . After how many successful calls, not counting misdials, will % of the users (including the PM) be a friend, or a friend of a friend etc., of the Prime Minister?
Every input file contains exactly one line with two integers separated by a single space: and .
is a -digit integer from to .
Output the only number - an answer to the problem.