Penguins of Madagaskar

তোমরা সবাই পেঙ্গুইনস অফ মাদাগাস্কারের কথা শুনেছ অবশ্যই ? এই পেঙ্গুইনেরা নিজেদের প্রগতির জন্য কাজ করে এবং সৌন্দর্যবোধ তাদের মধ্যে প্রবল। অক্টোপাস ডেভ একবার সারা বিশ্বের পেঙ্গুইনদের উপর আক্রমণ করে বসে। ডেভ বিশ্বের সব যায়গা থেকে পেঙ্গুইনদের ধরে তার ল্যাবে নিয়ে আসতে থাকে , শুধুমাত্র মাদাগাস্কারের চার পেঙ্গুইন Rico, Skipper,Kowalski আর Private-কে খুঁজে পায়না। ডেভের ল্যাবটি এমনভাবে নিরাপত্তাবেষ্টিত যে বাইরে থেকে কেউ সহজে ঢুকে আটক পেঙ্গুইনদের বাঁচাতে পারবেনা।

এই ঘটনার প্রেক্ষিতে মাদাগাস্কারের চার পেঙ্গুইন Rico, Skipper,Kowalski আর Private আটকে থাকা পেঙ্গুইনদের বাঁচাতে একটি অপারেশনের সিদ্ধান্ত নিল । অপারেশনের প্রথম ধাপ হল গোপন এবং সুরক্ষিত ল্যাবটিতে ঢুকতে পারা। ল্যাবে ঢুকতে হলে প্রথমেই একটি কম্পিউটারাইজড সিকিউরিটি সিস্টেমের সম্মুক্ষীন হতে হয়। এই সিস্টেম একটি গাণিতিক সমস্যা দেয় এবং ঢুকতে হলে এই সমস্যাটি সমাধান করতে হবে। প্রাইভেট সমস্যাটির সমাধান করে টিমের বাকীদের জন্য অপারেশনটি সহজ করে দেয়। তুমি কি পারবে এই সমস্যার সমাধান করতে ?

সমস্যাটি তোমার জন্য এখানে বর্ণনা করা হল।

প্রথমেই বলে রাখি এই গাণিতিক সমস্যাটিতে আমরা যেসব সংখ্যা নিয়ে কাজ করব তারা সবাই 105 ভিত্তির নাম্বার সিস্টেমে আছে। অর্থাৎ এসব নাম্বারে ডিজিটগুলো [০,৯৯৯৯৯] এই রেঞ্জে আছে। খেয়াল করতে হবে যে এখানে ৯৯৯৯৯ কিন্তু একটি ডিজিট। ১০৫ ভিত্তির নাম্বার সিস্টেমে একটি সংখ্যার উদাহরণ হলঃ

N = (১৫২)(১৬৩)(৯)(৯৯৯৮)

এখানে ১৫২,১৬৩,৯,৯৯৯৮ প্রত্যেকে একটি করে ডিজিট। সংখ্যাটিতে ডিজিটগুলোকে আলাদা করার জন্য আমরা প্রথম বন্ধনী ব্যাবহার করেছি যাতে তোমরা সহজে বুঝতে পার। এখানে ১৫২ হল সবচেয়ে বামের ডিজিট এবং এটিই হল Most Significant Digit এই নাম্বারের ক্ষেত্রে। একইভাবে বলয়া যায় ৯৯৯৮ হল সবচেয়ে ডানের ডিজিট এবং তাই এটিই হল Least Significant Digit এই নাম্বারের ক্ষেত্রে।

এখন তোমাদেরকে একটি লিস্ট L দেওয়া হবে, যে লিস্টে কিছু ডিজিট দেওয়া থাকবে। এই ডিজিটগুলোকে আমরা বলবো Beauty Digits । এরপর তোমাকে কিছু প্রশ্ন করা হবে। প্রতিটি প্রশ্নে তোমাকে দুইটি সংখ্যা A এবং B দেওয়া হবে ১০৫ ভিত্তির নাম্বার সিস্টেমে। তোমাকে F(A,B) ফাংশনটির মান বলতে হবে। F(A,B) কী তাইতো ? আচ্ছা F(A,B) ফাংশনটির আমাদেরকে বলে [A,B] রেঞ্জে মোট কতগুলো Beautiful Number আছে। Beautiful Number এর সংজ্ঞা হলোঃ

"যেসব সংখ্যায় লিস্ট L এর Beauty Digit-গুলো জোড়সংখ্যাকবার আছে তারা হলো Beautiful Number । "

105 ভিত্তির নাম্বার সিস্টেমে একটি পূর্ণসংখ্যার ডিজিটগুলো [০,৯৯৯৯৯] রেঞ্জের মধ্যে থাকবে। তোমাদের জন্য যেন সহজ হয় তাই আমরা A এর ডিজিটগুলোকে স্পেস দিয়ে আলাদা করে ইনপুট দিব এক লাইনে । আবার অন্য একটি লাইনেও B এর ডিজিটগুলোকেও স্পেস দিয়ে আলাদা করে করে ইনপুট দিব।

সমস্যাটির একটি উদাহরণ দেওয়া যাক। ধরো তোমার কাছে একটি Beauty Digit এর লিস্ট L দেওয়া হলো যেখানে ডিজিটগুলো হচ্ছে ১,২ এবং ৩ । এবার তোমাকে প্রশ্ন করা হলো A = 1 এবং B = 16 হলে [A,B] রেঞ্জে কতগুলো Beauty Number আছে ? উত্তর হল ১৩ টি Beauty Number আছে।

যেহেতু উত্তর অনেক বড় হতে পারে তাই তুমি উত্তরটিকে ১০০০০০০০০৭ দিয়ে ভাগ করে ভাগশেষটি প্রিন্ট করবে।

Input

ইনপুটের প্রথম লাইনে একটি পূর্ণসংখ্যা Z দেওয়া হবে। Z হল লিস্টে কতগুলো Beauty Digit দেওয়া হবে সেটা। পরের লাইনে Z টা পূর্ণসংখ্যা দেওয়া হবে যারা প্রত্যেকে Beauty Digit । এরপর নতুন লাইনে একটি সংখ্যা Q ইনপুট দেওয়া হবে । Q হল তোমাকে কতগুলো প্রশ্ন করা হবে সেই সংখ্যা বা কুয়েরির সংখ্যা। এরপর Q টি লাইনের প্রত্যেকটিতে তিনটি করে লাইন থাকবে। প্রথম লাইনে দুইটি পূর্ণসংখ্যা X এবং Y ইনপুট দেওয়া হবে। X দিয়ে বুঝায় A তে কতগুলো ডিজিট থাকবে , Y দিয়ে বুঝায় B তে কতগুলো ডিজিট থাকবে। দ্বিতীয় লাইনে A এর X টা ডিজিট তোমাকে দেওয়া হবে। ডিজিটগুলো স্পেস দিয়ে আলাদা করা থাকবে । তৃতীয় লাইনে B এর Y টা ডিজিট ইনপুট দেওয়া হবে। ডিজিটগুলো স্পেস দিয়ে আলাদা করা থাকবে।

For 30 points:
1<=Z<=10
1<=X,Y<=2
A,B will be within the range [ (1)(1) , (50)(99999)]

For 100 points:
1<=Z<=10
1<=Q<=1000
1<=X,Y<=1000

এবং ডিজিটগুলো ইনপুট দেওয়া হবে [১,৯৯৯৯৯] এই রেঞ্জের মধ্যে। এর মানে হলো তোমাকে যে দুটি সংখ্যা A এবং B দিব সেখানে কোন ডিজিট 0 হবে না। কিন্তু তুমি A থেকে B এর মধ্যে যেসব সংখ্যাগুলো বানাবে সেগুলোতে শূন্য থাকতেই পারে।
আর তোমাকে আমরা নিশ্চিত করছি যে A<=B এবং A,B এর কোন leading zero নেই ।

Output

আউটপুটঃ
প্রতিটি প্রশ্নের জন্য কোটেশন মার্ক ছাড়া প্রিন্ট করবে "Case x: y" যেখানে x হচ্ছে প্রশ্ন নম্বর এবং y হচ্ছে তোমার কাছ থেকে যে উত্তর জানতে চাওয়া হয়েছে সেটা। আরও ভালো করে বোঝার জন্য স্যাম্পল ইনপুট আউটপুট সেকশন দেখতে পার।

Sample

Input	Output
1 9 4 1 1 1 1 2 5 63 12 125 1 8 6 93 1 1 1 100 1 1 50 120	Case 1: 1 Case 2: 234105042 Case 3: 99 Case 4: 71