Yet Another Problem About gcd

题目描述

设：

$F(l,r)=\max\limits_{i=l}^{r}(\max\limits_{j=i+1}^{r}\gcd(i,j))$

试求 $\sum\limits_{j=l+1}^{r}F(l,j)\mod 993244853$

其中 $gcd(i,j)$ 表示 $i$ 和 $j$ 的最大公因数。

输入格式

$l\ r$

输出格式

$ans$

样例 #1

样例输入 #1

5 8

样例输出 #1

4

提示

样例解释

$F(5,6)=1$

$F(5,7)=1$

$F(5,8)=2$

所以答案为 $4$。

【数据范围】

$1 \le l,r \le 10^7$