六队-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