ধর একটা N*N আকারের ছক দেওয়া আছে যেখানে (r,c) মানে ছকের একটি ঘর। এখানে r মানে হল সারি আর c মানে হল কলাম। তুমি আছ (0,0) ঘরে আর তোমার বন্ধু আছে (N,N) ঘরে। তুমি (0,0) থেকে যাত্রা শুরু করে (N,N) ঘরে পৌছাতে চাও। তোমার বন্ধু (N,N) থেকে যাত্রা শুরু করে (0,0) ঘরে পৌছাতে চায়। তুমি কেবলমাত্র উপরের দিকে অথবা ডানে যেতে পারবে , তোমার বন্ধু কেবলমাত্র নীচের দিকে বা বামে যেতে পারবে।
তোমরা একই সাথে যাত্রা শুরু করেছ। প্রতি সেকেন্ডে তোমার বন্ধু এবং তুমি দুইজনেই এক ঘর থেকে আরেক ঘরে যাও। মানে এক ঘর থেকে আরেক ঘরে যাও উপরে যে নিয়মের কথা বলেছি সেই নিয়ম মেনে। তোমার যাত্রা শেষ হবে (N,N) ঘরে। আর তোমার বন্ধুর যাত্রা শেষ হবে (0,0) ঘরে। তোমাদের এই যাত্রাপথে যেকোন ঘরে দুইজনের দেখা হয়ে যেতে পারে।
এখন একটা ফাংশন F(x,y) এর কথা চিন্তা করা যাক যেখানে F(x,y) হল কত উপায়ে তোমরা (x,y) ঘরে দেখা করতে পার। দুইটা উপায় ভিন্ন হবে যদি তোমাদের মধ্যে অন্তত একজনের যাত্রার শুরু থেকে দেখা করার ঘর পর্যন্ত পথ অন্য উপায়ের পথের থেকে ভিন্ন হয়।
তোমাকে বের করতে হবে G(N)
যেহেতু G(N) অনেক বড় একটি সংখ্যা হতে পারে তাই তুমি প্রিন্ট করবে G(N) modulo 999377
তোমাদের সহজবোধ্য করার জন্য ঘর পরিবর্তনের ঘটনাটিকে নীচে পরিষ্কার করা হল।
তুমি যদি (r,c) ঘরে থাক তাহলে এক সেকেন্ডে তুমি যেতে পারবে (r+1,c) ঘরে অথবা (r,c+1) ঘরে।
তোমার বন্ধু যদি (r,c) ঘরে থাকে তাহলে এক সেকেন্ডে সে যেতে পারবে (r-1,c) ঘরে অথবা (r,c-1) ঘরে।
Input
ইনপুটের প্রথম লাইনে তোমাকে একটি পূর্ণসংখ্যা T দেওয়া হবে যেখানে T<=10000 । এখানে T হলো টেস্টকেসের সংখ্যা । এরপর প্রতি টেস্টকেসে একটি করে পূর্ণসংখ্যা N ইনপুট দেওয়া হবে। এখানে 1<=N<=1000000000000 । N হলো ছকের সাইজ অর্থাৎ এখানে সারি থাকবে 0 থেকে N পর্যন্ত আর কলাম থাকবে 0 থেকে N পর্যন্ত।
Output
প্রতি টেস্টকেসের জন্য কোটেশন মার্ক ছাড়া প্রিন্ট কর "Case x: y" যেখানে x হলো কত নম্বর টেস্টকেসের উত্তর দিচ্ছ সেটা আর y হলো প্রশ্নে যে উত্তর চেয়েছে সেটা। মনে রাখতে হবে যে উত্তরকে কিন্তু 999377 দিয়ে ভাগ করলে যে ভাগশেষ পাওয়া যায় সেটা প্রিন্ট করতে হবে।
Sample
| Input | Output |
|---|---|
2 1 2 | Case 1: 2 Case 2: 6 |
