নুমেরিকিউ শ্রিঙ্কও মেটিক(Numerico Shrink O'Matic)

CPU: 1s
Memory: 1024MB


সরুবা জাদু শিখতে চাচ্ছে। তো সে ব্লু মিস্ত্রাল পাহাড়ে উঠল যেখানে শহরের মেয়র মেরিথাউস – দ্যা ব্লু সেজ, প্রতি বৃহস্পতিবার ধ্যান এ বসে। অনেক ধাঁধা সমাধান করে যেগুলোর জন্যে মূর্তি নাড়ানাড়ি করতে হয়েছে এবং লাভার নদী ও আগুনের গর্ত পাড়ি দিয়ে সরুবা মেরিথাউস এর কাছে আসল। যখন সরুবা জাদু শিখার ইচ্ছা প্রকাশ করলো, মেরিথাউস তাকে পড়ালেখা করার উপদেশ দিল, কারন জাদুবিদ্যা অনেক ভয়ানক। কিন্তু সরুবা নাছোড়বান্দা। শেষমেশ মেরিথাউস রাজি হল। মেরিথাউস সরুবাকে নিরেহ একটি জাদু শিখানোর সিদ্ধান্ত নিল, যেটি তাকে অঙ্কতে সাহায্য করতে পারে। কিন্তু সরুবা অভিযোগ করলো যে সে এমন জাদু শিখতে চায় যেটি দিয়ে সে উড়তে পারে, বা টেলিপোর্ট করতে পারে, বা অনন্ত চকলেট ডোনাট যেন বানাতে পারে। অনেক বুঝানোর পরে সরুবা অঙ্কের জাদু শিখতে রাজি হল।

মেরিথাউস এক টুকরা কাগজ নিয়ে সরুবার জন্যে নির্দেশনা লিখা শুরু করলো। শেষ হওয়ার পর সে কাগজটিকে মুড়িয়ে সরুবাকে দিল এবং তাকে বাসায় গিয়ে শিখে নিতে বলল। বাসায় আসার পর সরুবা সাথে সাথে কাগজটি পড়া শুরু করল।

“জাদু হল নিজের ওপর বিশ্বাস রাখা, যদি তুমি সেটা করতে পারো, তাহলে তুমি যেকোনো কিছুই ঘটাতে পারবে।“

জাদুর নাম : নুমেরিকিউ শ্রিঙ্কও মেটিক বিবরণ : এটি যেকোনো দৈর্ঘের সংখ্যাকে একটি ডিজিট এ ছোটো করে ফেলতে পারে। এটি x-কে y-এ রুপান্তর করতে পারে, যেখানে y হচ্ছে x-এর ডিজিটের যোগফল। এটি এভাবে প্রত্যেকটি ফলকে ছোটো করতে থাকে যতক্ষণ নাহ সংখাতে শুধু একটি ডিজিট থাকে।

আবশ্যিক শর্ত : প্রতি ব্যবহারের জন্যে শুধু ৩ মানা লাগে। সাথে লাগে মনোযোগ এবং জীবনীশক্তি, যাতে বোকাদের মত ভুল না হয়।

ব্যবহার : অঙ্কের বাড়িরকাজ করতে ব্যবহার করা যায়। অভিযানের সময় নানান ধাঁধা সমাধান করতেও কাজে লাগতে পারে। দক্ষতা : ভাল দক্ষতা থাকলে বড় সংখ্যার জন্য আরো তাড়াতাড়ি এবং আর নিখুতভাবে হিসাব করা যাবে। অভিষেক : জাদুটি শিখার জন্যে, নিম্নের মন্ত্রটি ১০০০ বার পড়তে হবে। শিখার পর জাদুটি নিক্ষেপ করতে মন্ত্রটি একবার পড়াই যথেষ্ট।

“লূ লস বেলিএভিং ক হিন্মাআর, ওয়ান হি ভইস দ্রেহ তল, হি ভইস ওয়াহু নান ক্রস”

সরুবা সাথে সাথে জাদুটি শিখে ফেলল এবং অনুশীলন করা শুরু করে দিল। অনুশীলনের জন্যে সে N!-এর মান নিলো এবং তার ওপর “নুমেরিকিউ শ্রিঙ্কও মেটিক” জাদুটি ব্যবহার করলো। খুব তাড়াতাড়ি সে শিখে ফেলল জাদু। হতে পারে জাদু তার জন্যে অনেক স্বাভাবিক?

কিন্তু তার মনের গভীর কোনে একটি সন্দেহ জাগে। সে নিশ্চিত হতে চায় যে তার জাদু কাজ করছে। তো সে তোমার কাছে আসল সাহায্যের জন্যে। সে চায় তুমি একটি প্রোগ্রাম লেখো যেটি হুবহু জাদুর মত কাজ করবে N! এর ওপর। অর্থাৎ প্রোগ্রামটি N! এর ডিজিট এর যোগফল বের করতে থাকবে বারবার যতক্ষন নাহ সংখ্যাটি ছোটো হয়ে ১ ডিজিট না হয়ে যায়। উদাহরণস্বরূপ, যদি N=৯ হয়, তাহলে ৯!=৩৬২৮৮০। তাহলে সরুবা যখন জাদু ব্যবহার করবে, এটি হয়ে যাবে :

৩৬২৮৮০->৩+৬+২+৮+৮+০ = ২৭->২+৭->৯। তাহলে উত্তর হল ৯।

Soruba wants to learn magic. So he climbed Mountain of Blue Mistral where Merithaus - the Blue Sage, local town mayor meditates every Thursday. After crossing lava streams, fire pits and solving various puzzles that required shifting statutes from one place to another, Soruba manages to reach Merithaus. When Soruba expresses his desire to learn magic, Merithaus advises him to go and study instead, for magic is a dangerous tool which in hands of young and inexperienced will only bring malice over land. But Soruba kept on pestering Merithaus until he bent. Merithaus decided to teach a harmless magic to Soruba, that will help him with his math homeworks. Soruba complained that he would rather learn how to fly, teleport or at least make Chocolate Donuts. After few hours of lecture on “Theory of Knowledge”, Merithaus finally managed to convince Soruba that mathematics is important for magic. Afterwards, Merithaus took a ink-dipped quill and parchment, and started to write down the instruction for Soruba. When it was complete, he rolled the parchment into scroll and handed it to Soruba, instructing him to go home to learn it. After returning home, Soruba immediately opened the scroll and started reading it. “Magic is believing in yourself, if you can do that, you can make anything happen” Magic Name: Numerico Shrink O'Matic Description: It can shrink a number of any length to a single digit. It takes a number x and converts it to y, where y is the sum of digit of x. It keeps on shrinking the resultant numbers until the final result is a single digit. Requirement: Needs 3 mana for each use. Also needs high Concentration and Vitality so that silly mistakes do not occur. Use: Can be used to aid in Math homework. Might be useful in solving puzzles during adventure. Mastery: High mastery allows faster calculation of larger numbers with greater accuracy. Initiation: To learn the spell, recite the following verse 1000 times. After learning, repeating the verse once is enough to cast the spell. “Lu los believing ko hinmaar, waan hi vis dreh tol, hi vis wahl naan koros” Soruba immediately learned the spell and started to practice it. In order to practice he takes the value of N! and performs magic “Numerico Shrink O'Matic” on it. He got the hang of it pretty quickly. Perhaps he is a natural in magic?

But deep down in his heart, he was a bit skeptic. He wanted to be sure that the magic worked. So he came to you for help. He wants you to write a program, that will simulate the action of the magic on N!. That is, the program will find the sum of digit of N! repeatedly until the number shrinks to a single digit. For example, if N = 9, then 9! = 362880. So when Subaro applies the magic, it becomes:

362880 -> 3+6+2+8+8+0 = 27 -> 2 + 7 = 9. So the result is 9.


ইনপুটের বর্ণনা

প্রথম লাইনে থাকবে একটি ধনাত্মক সংখ্যা T (T <= ১০০), যেটি বুঝাবে কতগুলি টেস্ট কেস আছে। তারপর এর T লাইন এ থাকবে একটি ধনাত্মক সংখ্যা, N।

সাবটাস্ক১ : N <= ৮, ৩০ পয়েন্টের জন্য

সাবটাস্ক২ : N <= ১০০০, ৩০ পয়েন্টের জন্য

সাবটাস্ক২ : N <= ১,০০০,০০০,০০০, ৪০ পয়েন্টের জন্য


Input Specification

The first line contains a single integer T ( T <= 100 ), the number of test case. The next T lines contain a single positive integer N.

Subtask 1: N <= 8, for 30 points

Subtask 2: N <= 1000, for 30 points

Subtask 3: N <= 1,000,000,000, for 40 points


আউটপুটের বর্ণনা:

T টি লাইন আউটপুট করতে হবে, যার প্রথমে থাকবে কেস নাম্বার এবং তারপর একটি মাত্র ডিজিট সেটি হচ্ছে N!-এর ডিজিট এর মান যদি বারবার যোগ করে ছোটো করা হয়, তার মান। বিস্তারিত জানার জন্যে ইনপুট আউটপুট এর উদাহরণ দেখ।


Output Specification

For each case, print a single line containing the case number and then a single digit which is the result of repeatedly summing digits of N!.


Sample

InputOutput
5 1 2 3 4 5 Case 1: 1 Case 2: 2 Case 3: 6 Case 4: 6 Case 5: 3