weird-function

Chandu is working on Weird function these days. A weird function is defined as:
W(a,b) =  MW(a) + MW(a+1) + MW(a+2)... + MW(b) 
(a and b both inclusive)
where a and b are integers and MW is mini weird function, which is defined as:
MW(i) = p^i + q^i + ... 
where p and q (less than or equal to i) are all possible integers such that gcd(p,i) = p, gcd(q,i)= q ... and so on. 

For example:
MW(10) = 1^10 + 2^10 + 5^10 + 10^10
where gcd(1,10) = 1, gcd(2,10) = 2, gcd(5,10) = 5, gcd(10,10) = 10

Your task is to find W(a,b) for given a and b.  

Input:
First line of input contains an integer t, which is the number of test cases. Each test case contains a single line containing two integers a and b.

Output:
Print W(a,b) for each test case modulo 10^9 + 7.

Constraints:
1 ≤ a,b ≤ 10^4
1 ≤ t ≤ 10^5

SAMPLE INPUT
2
2 2
2 3

SAMPLE OUTPUT
5
33

Source: hackerearth | Difficulty: MEDIUM
Tags: Number theory

Mathematics


Solutions: