John Doe has a list of all Fibonacci numbers modulo 10¹³. This list is infinite, it starts with numbers 0 and 1. Each number in the list, apart from the first two, is a sum of previous two modulo 10¹³. That is, John's list is made from the Fibonacci numbers' list by replacing each number there by the remainder when divided by 10¹³.

John got interested in number f (0 ≤ f < 10¹³) and now wants to find its first occurrence in the list given above. Help John and find the number of the first occurence of number f in the list or otherwise state that number f does not occur in the list.

The numeration in John's list starts from zero. There, the 0-th position is the number 0, the 1-st position is the number 1, the 2-nd position is the number 1, the 3-rd position is the number 2, the 4-th position is the number 3 and so on. Thus, the beginning of the list looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...