UOJ Logo Sharp Sword 剑锋 OI

SSOI

#37. 最小公倍数求和

统计

再求和 ≤,≠,≥<>

【问题描述】

给出T组N和M,依次求出下图中公式的值

Markdown

【输入格式】

第一行一个T
接下来T行,每行两个正整数M和N

【输出格式】

输出T行,每行为对应的计算结果(对100000009取模)

【输入样例1】

2
3 6
100 200

【输出样例1】

96
73830168

【时空限制】

1S
256MB

【数据范围】

N,M≤10^6,T≤1000