وفقًا لاعتقاد شائع، يشرب المبرمجون الكثير من القهوة ولا يعرفون إلا بضع كلمات. تتكون مفردات المبرمج النموذجي من ثلاث كلمات فقط. وفوق ذلك، نادرًا ما يعرف كيفية تهجئتها. لمساعدة المبرمجين على معالجة أخطائهم الإملائية، نشرنا كتابًا بعنوان «قاموس الكلمات الثلاث التي ينبغي لكل مبرمج نموذجي أن يعرفها».

حصلت على نسخة من الكتاب، لكنك سكبت قهوتك عليها بعد ذلك بوقت قصير. والآن لا يمكنك قراءة بعض الأحرف. لحسن الحظ، كانت الكلمات الثلاث، كما هو معتاد في القواميس، مختلفة ومطبوعة بالترتيب المعجمي.

قبل أن تحاول الاستفادة من هذه الحقيقة لاستعادة الأحرف المفقودة، تريد معرفة عدد الطرق المختلفة للقيام بذلك. ولأنك تتوقع أن يكون هذا العدد كبيرًا، فإنك تريد معرفته بترديد $10^9 + 9$.

الإدخال

يحتوي السطر الأول من الإدخال على عدد حالات الاختبار $T$. تليه أوصاف حالات الاختبار:

تتكون كل حالة اختبار من ثلاثة أسطر، يحتوي كل منها على كلمة واحدة غير فارغة، حسب ترتيب ظهورها في القاموس. تتكون الكلمات من الأحرف الإنجليزية الصغيرة وعلامات الاقتباس، حيث تشير الأخيرة إلى الأحرف المفقودة. لا يتجاوز طول كل كلمة $1\,000\,000$ حرف.

لا يتجاوز حجم ملف الإدخال 16.0 MiB.

الإخراج

لكل حالة اختبار، اطبع سطرًا واحدًا يحتوي على عدد الطرق المختلفة لاستبدال كل علامة استفهام بأحد الأحرف الستة والعشرين من «a» إلى «z»، بحيث تكون الكلمات الثلاث مختلفة ومرتبة معجميًا. يجب طباعة العدد بترديد $10^9 + 9$.

أمثلة

الإدخال 1

3
?heoret?cal
c?mputer
?cience
jagiellonian
?niversity
kra?ow
?
b
c

الإخراج 1

42562
52
1