Fiborooji Sequence

Interview

Time limit1sMemory limit1024 MB

Summary

Given two starting digits, generate each next term as the last digit of the sum of the previous two, and find the cycle length until the starting pair repeats.

Level: Easy3 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Problem

The Fibonacci sequence is defined as follows:

$F_0 = 0$
$F_1 = 1$
$F_n = F_{n-1} + F_{n-2}$ for n ≥ 2

The numbers in this sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … The Fibonacci sequence has many applications in mathematics, computer science, nature, economics, art, and music.

The Fiborooji sequence is a simplified version of the Fibonacci sequence. It starts with two single-digit, non-negative numbers, at least one of which is nonzero. Each following number is the sum of the two numbers before it, but the numbers always stay single digit. If the sum has two digits, only its rightmost digit becomes the next number. For example, after 8 and 7, the sum is 15, but the next number is 5, not 15. After 4 and 6, the sum is 10, but the next number is 0, not 10. Starting with 2 and 1, the sequence is 2, 1, 3, 4, 7, 1, 8, 9, 7, 6, …

The sequence repeats no matter which two single-digit numbers you start with. After a while, the two starting numbers appear again, so the sequence cycles through the same numbers.

Input

There is only one input line. It contains two single-digit, non-negative numbers, at least one of which is non-zero.

Output

Print the length of the sequence when the starting two numbers repeat.

Hint

Explanation of the first sample: the sequence is 3, 4, 7, 1, 8, 9, 7, 6, 3, 9, 2, 1, 3, 4, which has length 14. The sequence started with 3 4, and the pair 3 4 appears again consecutively at the 14th element.

Examples4

Example 1
Input
```
3 4
```
Expected output
```
14
```
Example 2
Input
```
0 6
```
Expected output
```
22
```
Example 3
Input
```
1 0
```
Expected output
```
62
```
Example 4
Input
```
5 5
```
Expected output
```
5
```