A Girl Has No Name

"জোফ্রে... সার্সেই... ইলিন পেইন... হাউন.." - আরিয়া স্টার্ক

গার্ডেন অফ বোনস, গেম অফ থ্রোনস S02E04

আরিয়া স্টার্ক HBO এর মহাকাব্যিক টেলিভিশন সিরিজ গেম অফ থ্রোনস এর স্টার্ক পরিবারের গুরুত্বপূর্ণ সদস্য।

আরিয়া এর একটি মৃত্যুতালিকা ছিল। যারা তার জীবনে কষ্ট বয়ে এনেছিল, সে তাদের হত্যা করতে চায়। কিন্তু সে খুব ছোট, তাই সে এখনই কাউকে হত্যা করতে পারবে না।
জাদুকরী ক্ষমতা শেখার জন্য সে ব্রাভোস এ যাওয়ার সিদ্ধান্ত নিল।

আরিয়া'র শিক্ষক তাকে একটি বিশাল কাজ দিয়েছিলো। তাকে নিজের কম্পিউটারে একটি জাদুর কোড চালাতে হয়।

func (L, R){
    sum = 0
    for (i = L; i <= R; i++){
        sum += score (i)
    }
    return sum
}

যেখানে,

score (N){
    A = number of unique non zero digits of N
    B = number of unique digits of N which evenly divides N
    return power (B, A)    //B to the power A
}

সে জাদুর ক্ষমতাবলে তার কম্পিউটারে খুব সহজেই এটি করতে পেরেছিল। তুমি কি পারবে?

Input

ইনপুট শুরু হয় একটি ইন্টিজার T (≤ 10) দিয়ে, যেটি টেস্টকেস এর সংখ্যা বোঝায়। প্রতিটি টেস্টকেসে এক লাইনে দুইটি ইন্টিজার থাকবে L R.

Scoring

সাবটাস্ক ১ (২০ পয়েন্টের জন্য): 1 ≤ T ≤ 10 1 ≤ L ≤ R ≤ 107

সাবটাস্ক ২ (৪০ পয়েন্টের জন্য): 1 ≤ T ≤ 5 1 ≤ L ≤ R ≤ 1014

সাবটাস্ক ৩ (৪০ পয়েন্টের জন্য): T = 1 1 ≤ L ≤ R ≤ 1018

Output

প্রতি টেস্টকেস এর জন্য, func (L, R) mod (109 + 7) প্রিন্ট করতে হবে।

Sample

Input	Output
3 1 10 12 15 20 100000	10 10 2522331