签到题

题目背景

这是一道签到题! **建议做题之前仔细阅读数据范围!**

题目描述

我们定义一个函数:qiandao(x)为小于等于x的数中与x**不互质**的数的个数。 这题作为签到题,给出l和r,要求求$\sum_{i=l}^r qiandao(i)~mod~666623333$。

输入输出格式

输入格式


一行两个整数,l、r。

输出格式


一行一个整数表示答案。

输入输出样例

输入样例 #1

233 2333

输出样例 #1

1056499

输入样例 #2

2333333333 2333666666

输出样例 #2

153096296

说明

对于30%的数据,$l,r\leq 10^3$。 对于60%的数据,$l,r\leq 10^7$。 对于100%的数据,$1 \leq l \leq r \leq 10^{12}$,$r-l \leq 10^6$。