+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو پس از به ارث بردن مقدار زیادی پول به دنبال راهی برای سرمایه گذاری بود تا بتواند بیشتر درآمد داشته باشد. پس از مشورت با دوستان خود به این نتیحه رسید که مغازه‌ای باز کند و در آن مکعب روبیک بفروشد. دوست عمو برای مغازه او $k$ روبیک آورده است که هر کدام به شکل یک مکعب مربع هستند. هر مکعب شامل $ n \times n \times n $ مکعب $ 1\times 1\times 1 $ است که ابعاد همه آن‌ها یکسان است. عمو برای اینکه فروش خود را بیشتر کند، سعی میکند که بعضی خانه های مجاور روبیک را به هم بچسباند به طوری که هر کدام به شکل یک روبیک با ابعاد دیگر باشد. همچنین لازم است که پس از چسباندن و تبدیل آن به روبیک با ابعاد کوچک‌تر هر تعداد چرخش مجاز در روبیک جدید قابل انجام باشد. (خانه های به هم چسبیده جدا نشوند و شکل کلی نیز از مکعب مربع خارج نشود). حال عمو از شما می‌خواهد که بگویید به ازای هر مکعب با ابعاد $n \times n \times n$ چند عدد $m$ وجود دارد که بتوان آن را با چسب زدن به $m \times m \times m$ تبدیل کرد. برای درک بهتر سوال به نمونه ورودی توجه کنید. # ورودی در خط اول ورودی شامل عدد $k$ که نشانگر تعداد روبیک های موجود در مغازه است، داده می‌شود. در $k$ خط بعدی در هر خط ابعاد هر یک از روبیک ها داده می‌شود. # خروجی به ازای هر روبیک بگویید که به عنوان چه روبیک هایی قابل فروختن است. # محدودیت‌ها $$1 \leq k \leq 1000$$ $$1 \leq n \leq 1000$$ ## ورودی نمونه ۱ ``` 2 3 4 ``` ## خروجی نمونه ۱ ``` 2 4 ``` مکعب ۳ در ۳ در ۳ فقط به عنوان مکعب ۳ در ۳ در ۳ و ۱ در ۱ در ۱ قابل فروش است. مکعب ۴ در ۴ در ۴ را میتوان به عنوان ۲ در ۲ در ۲ فروخت. (چسباندن خانه ها گوشه به تمامی خانه های مجاور راسی آن ها). به عنوان ۳ در ۳ در ۳ نیز میتوان فروخت، به این صورت که مرکز های مجاور را به هم میچسباند و وسط اضلاع را نیز به هم چسب میزند). به عنوان ۴ در ۴ در ۴ و ۱ در ۱ در ۱ نیز میتوان فروخت. در شکل زیر تبدیل ۴ در ۴ در ۴ به دو حالت گفته شده نشان داده شده. (خانه ها مجاور همرنگ به هم چسبیده اند).