One day Raghav was experimenting with the numbers to make new algorithms. He introduce a new term Rsum. Rsum of any number is defined as number obtained by iterative summing of digits of the given number until single digit number is obtained. For example: 365 --> (3+6+5) = 14 14 --> 1+4 = 5 Rsum(365)=5

Naughty Vinay came in the room of Raghav in his absence and change all the numbers on which Raghav was experimenting by their corresponding factorials. For example Vinay will change 3 with 6 (3!=321). Consider 0!=0.

When Raghav starts experimenting without knowing that the numbers are now changed. He got some ambiguous results and unable to find some pattern for his algorithm. So he wants your help. You are given a range [A,B] of actual numbers and your task is to find sum of all Rsum values in range [A,B] of new changed numbers.

Input: First line consist of T test cases. Next T line contain two integers a,b in each line.

Output: Find Sum of Rsum of all numbers in given range [A,B].

Constraints: 1<=T<=105 0<=A<=B<=106