시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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
W3sicHJvYmxlbV9pZCI6IjM3MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ0NWMiLCJkZXNjcmlwdGlvbiI6IlxyXG48cD5cclxuXHRuXHVkNTg5LCBtXHVjNWY0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQ0NWNcdWM1ZDAgMzJcdWJlNDRcdWQyYjggXHViZDgwXHVkNjM4XHVjNzg4XHViMjk0IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4MDBcdWM3YTVcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM4MWNcdWM3N2MgXHVjNjdjXHVjYWJkIFx1YzVmNFx1Yzc0MCAxXHVjNzc0XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVhYzA4IFx1YzIxOFx1Yjg1ZCBcdWJjODhcdWQ2MzhcdWFjMDAgMVx1YzUyOSBcdWM5OWRcdWFjMDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdEFpKDEgJmxlOyBpICZsZTsgbSlcdWI5N2MgaVx1YmM4OCBcdWM1ZjRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyMThcdWM3NTggXHVhY2YxXHVjNzNjXHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViNTRjLCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWMxMlx1Yzc0NCBcdWFjMTZcdWIyOTQgXHVjNWY0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVhZGY4XHViN2VjXHVkNTVjIFx1YzVmNFx1Yzc3NCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWI3N2NcdWJhNzQsIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzVmNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IG1cdWFjZmMgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbSAmbGU7IDIwLCAxICZsZTsgbiAmbGU7IDEwMDApIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBtXHVhYzFjXHVjNzU4IDMyXHViZTQ0XHVkMmI4IFx1YmQ4MFx1ZDYzOFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWNmMVx1Yzc0NCBcdWFjMTZcdWIyOTQgXHVjNWY0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzcyNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBUYWJsZSIsImRlc2NyaXB0aW9uIjoiPHA+Q29uc2lkZXIgdGhlIHRhYmxlIG9mIDMyLWJpdCBzaWduZWQgaW50ZWdlcnMgd2l0aCBuIHJvd3MgYW5kIG0gY29sdW1ucy4gVGhlIGNvbHVtbnMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBtIGJlZ2lubmluZyBmcm9tIHRoZSBsZWZ0IHNpZGUgb2YgdGhlIHRhYmxlLiBMZXQgQWkgKDEgJmxlOyBpICZsZTsgbSkgaXMgdGhlIHByb2R1Y3Qgb2YgYWxsIG51bWJlcnMgaW4gdGhlIGktdGggY29sdW1uLiBGaW5kIHRoZSBtYXhpbXVtIG9mIHRoZXNlIHByb2R1Y3RzIGFuZCBwcmludCB0aGUgY29sdW1uIG51bWJlciB3aGVyZSB0aGlzIG1heGltdW0gcHJvZHVjdCBpcyBhY2hpZXZlZC4gSWYgdGhlcmUgYXJlIG1hbnkgc3VjaCBjb2x1bW5zLCBwcmludCB0aGUgbGFyZ2VzdCBudW1iZXIgb2YgdGhlIGNvbHVtbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkNvbnNpc3RzIG9mIG11bHRpcGxlIHRlc3RzLiBFYWNoIHRlc3QgYmVnaW5zIHdpdGggYSBsaW5lIHdpdGggdHdvIGludGVnZXJzIG0gYW5kIG4gKDEgJmxlOyBtICZsZTsgMjAsIDEgJmxlOyBuICZsZTsgMTAwMCkuIEVhY2ggb2YgdGhlIG5leHQgbiBsaW5lcyBjb250YWlucyBtIDMyLWJpdCBzaWduZWQgaW50ZWdlcnMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIHByaW50IG9uIGEgc2VwYXJhdGUgbGluZSB0aGUgY29sdW1uIG51bWJlciB3aXRoIHRoZSBtYXhpbXVtIHByb2R1Y3QuIElmIHRoZXJlIGFyZSBzZXZlcmFsIG9mIHRoZW0gJm5kYXNoOyBwcmludCB0aGUgbGFyZ2VzdCBudW1iZXIgb2Ygc3VjaCBjb2x1bW4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d