Деталі
Вибір складається з N деталей. Є N верстатів, на кожному з яких можна виготовити довільну деталь. Для кожних верстату та деталі відомий час t[i, k] виготовлення k-ї деталі на i-му верстаті.
Напишіть програму, яка визначає, на якому верстаті потрібно виготовити кожну деталь, щоб одночасно почавши виготовляти усі детали, завершити виготовленне усіх деталей якомога скоріше.
Вхідні дані
Перший рядок вхідного файлу містить кількість тестів. Перший рядок кожного тесту містить кількість верстатів та деталей N (1 ≤ N ≤ 50). Кожен з наступних N рядків містить тривалості виготовлення деталей на відповідному верстаті t[i,1], t[i,2], ..., t[i,N], відокремлені комами. Кожне з цих чисел натуральне і не перевищує 100.
Коректність вхідних даних гаранується.
Вихідні дані
У вихідний файл для кожного тесту потрібно послідовно вивести в один рядок номери деталей, які потрібно виготовити відповідно на 1-му, 2-му, ..., N-му верстатах, відокремивши їх пропусками. У наступний рядок потрібно вивести час від початку до завершення виготовлення усіх деталей.
Для кожного тесту достатньо знайти один розв'язок.