Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem G: 六队-Utopian and River

Problem G: 六队-Utopian and River

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 15  Solved: 4
[Submit][Status][Web Board]

Description

Utopian主持开发了一条航道。由于他最近对数的互质非常感兴趣,这条航道的开发也就很明显的运用了这种规律。这条总设计长度为1000km的航道,被均匀地划分为10,000,000段,并依次标记(1-10000000),且每段的深度由该段的编号决定:的值为所有在区间内与互质的数的和对1e9+7取模的结果。

​ 在航道开发过程中,Utopian收到很多航运公司的询问,想要获知在编号区间分别为的航段内(包括左端点,不包括右端点),最浅深度为多少?

Input

仅单组数据。

给定一个Q,表示Utopian共收到了多少的询问,保证询问数在1000000左右。

下列Q行,每行给出,,保证, 且

Output

对于每个询问输出Case #i: mindep,i为第几个询问,mindep为区间最浅深度。

Sample Input

6
202190 130
507167 7117
31126 433166
222959 22879
26721 327781
36491 31441

Sample Output

Case #1: 2640
Case #2: 5192
Case #3: 5192
Case #4: 6845
Case #5: 6845
Case #6: 108662400

HINT

[Submit][Status][Web Board]