Check-in Challenge: Counting Non-Coprime Numbers

We define a function \(\operatorname{qiandao}(x)\) as the number of integers \(n\) (with \(1 \le n \le x\)) that are not coprime with \(x\). In other words,

\[ \operatorname{qiandao}(x) = x - \varphi(x), \]

where \(\varphi(x)\) is Euler's totient function.

This is a simple check-in problem. Given two integers \(l\) and \(r\), compute:

\[ S = \sum_{i=l}^{r} \operatorname{qiandao}(i) \bmod 666623333. \]

Please note that all formulas are rendered using LaTeX.

inputFormat

The input consists of a single line containing two space-separated integers \(l\) and \(r\) (with \(1 \le l \le r\)).

For example:

1 3

outputFormat

Output a single integer: the value of \(S = \sum_{i=l}^{r} \operatorname{qiandao}(i) \bmod 666623333\).

For example, for the input above, the output should be

2

sample

1 1

0