একটি সুপার শপ কেবল ২৬ টি পণ্য বিক্রি করে। এই পণ্যগুলো 'A' থেকে 'Z' অক্ষর দ্বারা লেবেল করা হয়। সুপার শপটি প্রত্যেক গ্রাহকের ক্রয়কৃত পণ্যের তালিকা সংরক্ষণ করে, যাকে বলা হয় ট্রান্সেকশন।
একটি ট্রান্সেকশন হল, একজন গ্রাহকের দ্বারা ক্রয়কৃত পণ্যগুলোর সেট, যেই সেটটি একটি স্ট্রিং দ্বারা প্রকাশ করা হয়। উদাহরণস্বরূপ “ACGBD” হল একটি ট্রান্সেকশন যার অর্থ পণ্য A, C, G, B, D একটি নির্দিষ্ট গ্রাহক কিনেছেন। নোট করুন যে, একটি ট্রান্সেকশন স্ট্রিংয়ের প্রতিটি অক্ষর আলাদা আলাদা।
দিন শেষে সুপার শপটির কাছে ণ সংখ্যক ট্রান্সেকশন এর তালিকা আছে।
এখন, ধরি X এবং Y দুটি পণ্যের সেট এবং [X ∩ Y = 𝜙], এটার মানে হল X এবং Y এর কোন সাধারণ উপাদান নেই। উদাহরণস্বরূপ X = “ABD” এবং Y = “CEF” সঠিক, যেখানে X = “ABC” এবং Y = “CDE ” সঠিক নয়।
এটি সত্যি যে, এখানে কমপক্ষে একটি ট্রান্সেকশন স্ট্রিং রয়েছে যেখানে সেট X এর সমস্ত উপাদান(অক্ষর) রয়েছে।
এখন আপনাকে N সংখ্যক ট্রান্সেকশন এর একটি তালিকা দেওয়া হবে। কোন একটি ট্রান্সেকশন স্ট্রিং এ X এর সকল উপাদান থাকলে, ঐ একই ট্রান্সেকশন স্ট্রিং এ Y এর সকল উপাদান থাকার সম্ভাব্যতা খুঁজে বের করতে হবে।
Input
প্রথম লাইনে টেস্ট কেস এর সংখ্যা t (t ≤ 20) রয়েছে।
প্রতিটি টেস্ট কেস এর ক্ষেত্রে প্রথম লাইনে দুটি পূর্ণসংখ্যা N এবং M (1 ≤ N, M ≤ 1000) থাকে। পরবর্তী N সংখ্যক লাইনের প্রতিটা লাইনে একটি ট্রান্সেকশন স্ট্রিং T (1 ≤ T ≤ 26) থাকবে , ট্রান্সেকশন স্ট্রিং টি কেবলমাত্র বড় হাতের অক্ষর দিয়ে গঠিত ।
তারপর M সংখ্যক কোয়েরি থাকবে। প্রতিটি কোয়েরি তে দুটি লাইন থাকে। প্রথম লাইনটি X এবং দ্বিতীয় লাইনটি হল Y, (1 ≤ | X |, | Y | ≤ 26)
Output
প্রতিটি টেস্ট কেস এর ক্ষেত্রে প্রথমে “Case #:” থাকবে (যেখানে “#” কেস নম্বর, 1 থেকে শুরু হবে)। তারপর একটি নতুন লাইন প্রিন্ট করতে হবে।
তারপর M সংখ্যক লাইন প্রিন্ট করতে হবে। M লাইনগুলোর প্রতিটিতে একটি দশমিক সংখ্যা P (2 দশমিক স্থান পর্যন্ত) প্রিন্ট করতে হবে।
P হচ্ছে কোন একটি ট্রান্সেকশন স্ট্রিং এ X এর সকল উপাদান থাকলে, ঐ একই ট্রান্সেকশন স্ট্রিং এ Y এর সকল উপাদান থাকার সম্ভাব্যতা
Sample
| Input | Output |
|---|---|
2 3 3 ABCDE ABD ACD A B AC D EA Z 2 1 XACDEGHTNOIK ZXTANIKGCH ACGH TONIK | Case 1: 0.67 1.00 0.00 Case 2: 0.50 |
