Masala #0650

\(K\) ranglardan foydalanib \(N \times M\) panjarani rang berish usullari sonini hisoblang. Panjaradagi qo'shni kvadratlar bir xil ranglarga ega bo'lishi mumkin. Sizning vazifangiz \(K\) ranglarda foydalanib ushbu panjarani eng kam bo'yash usulini toping.

• Birinchi qatorda \(T (1 \le T \le 15)\)  testlar soni kiritiladi.
• Keyingi T ta qatorda \(N,M (1 \le N , M \le 8)\) va \(K (1 \le K \le 10^{18})\) sonlari kiritiladi.

Chiqish faylining birinchi qatorida har bir test uchun natijalarni probel bilan ajratilingan holda chop eting