题目描述

求 $\sum^{n}_{i=1} \sum^{m}_{j=1} \operatorname{lcm}(i,j)$，对答案 $\bmod 10^8+9$。

输入格式

一个正整数 $T$ 表示数据组数。

接下来 $T$ 行，每行两个正整数，表示 $n,m$。

输出格式

$T$ 行，每行一个整数，表示第 $i$ 组数据的结果。

数据规模与约定

$1\le T \le 10^4$，$1\le n,m \le 10^7$。