1047 - Substring of FizzBuzz

面接官「FizzBuzz書けますか？」

応募者「はい！」

面接官「では、

問題文

初め、文字列 $S$ は空文字列である。
$n=1, 2, ... 10^{100}$ について、$n$ が3で割り切れるならFizzを、5で割り切れるならBuzzを、両方で割り切れるならFizzBuzzを $S$ の末尾に連結させる。
最終的な文字列 $S$ の最初の一部分は FizzBuzzFizzFizzBuzzFizzFizzBuzzFizzBuzzFizzFizzBuzzFizzFizz となる。
最終的な文字列 $S$ の $a$ 文字目から $k$ 文字の部分文字列と $b$ 文字目から $k$ 文字の部分文字列のハミング距離を求めなさい。

入力

$a, b, k$ が空白区切りで順に1行入力される。
$1≦a, b, k≦10^{17}$

出力

答えを1行に出力せよ。

サンプル

入力例1

1 2 10

出力例1

8

最終的な文字列 $S$ の $1$ 文字目から $10$ 文字の部分文字列は FizzBuzzFi である。
最終的な文字列 $S$ の $2$ 文字目から $10$ 文字の部分文字列は izzBuzzFiz である。
よって、ハミング距離は $8$ となる。

入力例2

1 5 20

出力例2

8

最終的な文字列 $S$ の $1$ 文字目から $20$ 文字の部分文字列は FizzBuzzFizzFizzBuzz である。
最終的な文字列 $S$ の $5$ 文字目から $20$ 文字の部分文字列は BuzzFizzFizzBuzzFizz である。
よって、ハミング距離は $8$ となる。

入力例3

114 514 810

出力例3

304

入力例4

31415926535897932 38462643383279502 12345678901234567

出力例4

12345678901234567

入力例5

31415926535897932 38462643383279500 12345678901234567

出力例5

0