시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 25 4 4 36.364%

문제

n행, m열로 이루어진 표에 32비트 부호있는 정수가 저장되어 있다. 제일 왼쪽 열은 1이고, 오른쪽으로 갈 수록 번호가 1씩 증가한다.

Ai(1 ≤ i ≤ m)를 i번 열에 있는 모든 수의 곱으로 정의하자. 이 때, 가장 큰 값을 갖는 열의 번호를 찾는 프로그램을 작성하시오. 그러한 열이 여러개라면, 번호가 가장 큰 열을 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 m과 n이 주어진다. (1 ≤ m ≤ 20, 1 ≤ n ≤ 1000) 다음 N개 줄에는 m개의 32비트 부호있는 정수가 주어진다.

출력

각 테스트 케이스에 대해서 한 줄에 하나씩 가장 큰 곱을 갖는 열의 번호를 출력한다.

예제 입력 1

2
3 3
20 10 30
15 20 20
30 30 20
3 2
2 -2 2
2 -2 2

예제 출력 1

3
3
W3sicHJvYmxlbV9pZCI6IjM3MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ0NWMiLCJkZXNjcmlwdGlvbiI6IlxyXG48cD5cclxuXHRuXHVkNTg5LCBtXHVjNWY0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQ0NWNcdWM1ZDAgMzJcdWJlNDRcdWQyYjggXHViZDgwXHVkNjM4XHVjNzg4XHViMjk0IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4MDBcdWM3YTVcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM4MWNcdWM3N2MgXHVjNjdjXHVjYWJkIFx1YzVmNFx1Yzc0MCAxXHVjNzc0XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVhYzA4IFx1YzIxOFx1Yjg1ZCBcdWJjODhcdWQ2MzhcdWFjMDAgMVx1YzUyOSBcdWM5OWRcdWFjMDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdEFpKDEgJmxlOyBpICZsZTsgbSlcdWI5N2MgaVx1YmM4OCBcdWM1ZjRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyMThcdWM3NTggXHVhY2YxXHVjNzNjXHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU1OFx1Yzc5MC4gXHVjNzc0IFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjMTJcdWM3NDQgXHVhYzE2XHViMjk0IFx1YzVmNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWM1ZjRcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzFjXHViNzdjXHViYTc0LCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM1ZjRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBtXHVhY2ZjIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG0gJmxlOyAyMCwgMSAmbGU7IG4gJmxlOyAxMDAwKSBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgbVx1YWMxY1x1Yzc1OCAzMlx1YmU0NFx1ZDJiOCBcdWJkODBcdWQ2MzhcdWM3ODhcdWIyOTQgXHVjODE1XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjZjFcdWM3NDQgXHVhYzE2XHViMjk0IFx1YzVmNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM3MjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgVGFibGUiLCJkZXNjcmlwdGlvbiI6IjxwPkNvbnNpZGVyIHRoZSB0YWJsZSBvZiAzMi1iaXQgc2lnbmVkIGludGVnZXJzIHdpdGggbiByb3dzIGFuZCBtIGNvbHVtbnMuIFRoZSBjb2x1bW5zIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbSBiZWdpbm5pbmcgZnJvbSB0aGUgbGVmdCBzaWRlIG9mIHRoZSB0YWJsZS4gTGV0IEFpICgxICZsZTsgaSAmbGU7IG0pIGlzIHRoZSBwcm9kdWN0IG9mIGFsbCBudW1iZXJzIGluIHRoZSBpLXRoIGNvbHVtbi4gRmluZCB0aGUgbWF4aW11bSBvZiB0aGVzZSBwcm9kdWN0cyBhbmQgcHJpbnQgdGhlIGNvbHVtbiBudW1iZXIgd2hlcmUgdGhpcyBtYXhpbXVtIHByb2R1Y3QgaXMgYWNoaWV2ZWQuIElmIHRoZXJlIGFyZSBtYW55IHN1Y2ggY29sdW1ucywgcHJpbnQgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIHRoZSBjb2x1bW4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Db25zaXN0cyBvZiBtdWx0aXBsZSB0ZXN0cy4gRWFjaCB0ZXN0IGJlZ2lucyB3aXRoIGEgbGluZSB3aXRoIHR3byBpbnRlZ2VycyBtIGFuZCBuICgxICZsZTsgbSAmbGU7IDIwLCAxICZsZTsgbiAmbGU7IDEwMDApLiBFYWNoIG9mIHRoZSBuZXh0IG4gbGluZXMgY29udGFpbnMgbSAzMi1iaXQgc2lnbmVkIGludGVnZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBwcmludCBvbiBhIHNlcGFyYXRlIGxpbmUgdGhlIGNvbHVtbiBudW1iZXIgd2l0aCB0aGUgbWF4aW11bSBwcm9kdWN0LiBJZiB0aGVyZSBhcmUgc2V2ZXJhbCBvZiB0aGVtICZuZGFzaDsgcHJpbnQgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIHN1Y2ggY29sdW1uLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==