题目描述

有一天，小Q梦见自己来到了理想国的幻想之乡。

有一天，小Q梦见自己来到了理想国的幻想之乡。幻想乡有无穷户居民，第 $i$ 个家庭住在编号为 $i$ 的房屋里，编号从 $1$ 开始，到正无穷。

居民们的房屋之间有着许多种道路，其中第 $k$ 种道路只连接在编号为 $k$ 的倍数且在 $k$ 的倍数中连续的房屋之间。例 如第 $1$ 种道路连接在编号为 $(1,2),(2,3),(3,4)\dots$ 的房屋之间，而第 $3$ 种道路只连接在编号为 $(3,6),(6,9),(9,12)\dots$ 的房屋 之间。

小Q要抓紧睡梦的时间来拜访幻想之乡中的贵人，他希望你能帮他完成这场幻想之旅。他经常会从某个编号为 $i$ 的房屋只走某种道路快速到达某个编号为 $j$ 的房屋，比如说从编号为 $4$ 的房屋走到编号为 $8$ 的房屋，可以走 $4->5->6->7->8$，也可以走 $4->6->8$，甚至可以走 $4->8$ 一步到达目的地。

他很好奇，如果他的起点房屋的编号是不大于 $n$ 的，终点房屋的编号是不大于 $m$ 的，对于所有可能的起点与终点，他最少会走多少条路，注意他的移动只会选择一种道路。

为了避免精度误差，他希望你能告诉他所有可能的起点与终点所对应的经过的最少边数之和。

由于这个数可能超过 $10^{18}$，但是不会很大，所以你只需要求出它对两个质数 $10^9+7$ 和 $10^9+9$ 的模值即可，小Q的数学很好，他会算出原来的答案。

输入格式

第一行一个正整数 $T$，表示小Q有 $T$ 组好奇的问题。 接下来是 $T$ 组问题，每组问题占一行，共两个正整数 $n, m$，空格隔开。

输出格式

共 $T$ 行，每行两个空格隔开的整数，表示每组问题分别模 $10^9+7$ 和 $10^9+9$ 的答案。

2
3 3
2 4

8 8
9 9

数据范围

对于 $100\%$ 的数据，$T\le 1000,n,m\le 2*10^6$。