One day, Touma Kazusa encountered a easy math problem. Given nn and kk, she need to calculate the following sum modulo 1e9+71e9+7.
∑ni=1∑nj=1gcd(i,j)klcm(i,j)[gcd(i,j)∈prime]%(1e9+7)∑i=1n∑j=1ngcd(i,j)klcm(i,j)[gcd(i,j)∈prime]%(1e9+7)
However, as a poor student, Kazusa obviously did not, so Touma Kazusa went to ask Kitahara Haruki. But Kitahara Haruki is too busy, in order to prove that he is a skilled man, so he threw this problem to you. Can you answer this easy math problem quickly?
Input
There are multiple test cases.（T=5） The first line of the input contains an integer T, indicating the number of test cases. For each test case:
There are only two positive integers nn and kk which are separated by spaces.