Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Meena's Fibonaccina

Limits 2s, 512 MB

Meena likes Fibonaccina numbers a lot. She gave Raju an assignment on Fibonaccina numbers. So Raju asks for your help as he knows that you are a good programmer.

First 6 Fibonaccina numbers are: 1 2 3 4 4 7.

Fibonaccina sequence can be constructed this way:

For N < 4:

f(0) = 1
f(1) = 2
f(2) = 3
f(3) = 4

For N ≥ 4:

if N is odd:
f(N) = f(N-1) + f(N-3)
else if N is even:
f(N) = f(N-2) + f(N-4)

Now, you are given L and R. You need to calculate how many distinct digits are there from f(L) to f(R) if we only consider the last digits of them.

Let’s say L = 2 and R = 5.

The digits are 3, 4, 4 and 7.

So there are 3 distinct digits (3, 4 and 7). Hence the answer is 3.

Input

The only line of the input contains two integers L (0 ≤ L ≤ 230) and R (0 ≤ R ≤ 230).

Output

Output an integer, the number of distinct digits from f(L) to f(R).

InputOutput
2 5
3
InputOutput
0 5
5

Discussion
Statistics
Submit