Table

Time limit1sMemory limit128 MB

Summary
Given an N by M table, compute each column's product and output the column index (largest index on tie) with the maximum product, handling big products across up to 1000 rows.
Level

Medium4 of 10

Topics
Math, Simulation, Array
Solved
No attempts yet

Problem

A table with NN rows and MM columns stores 32-bit signed integers. The leftmost column is numbered 1, and the column numbers increase by 1 toward the right.

For each column ii (1≤i≤M1 \le i \le M), let AiA_i be the product of all the numbers in that column. Write a program that finds the number of the column with the largest value. If several columns share the largest value, print the one with the largest column number.

Input

The first line contains the number of test cases TT.

The first line of each test case contains the number of columns MM and the number of rows NN (1≤M≤201 \le M \le 20, 1≤N≤10001 \le N \le 1000). Each of the following NN lines contains MM 32-bit signed integers.

Output

For each test case, print on its own line the number of the column with the largest product.

Examples1

  1. Example 1

    Input
    2
3 3
20 10 30
15 20 20
30 30 20
3 2
2 -2 2
2 -2 2
    Expected output
    3
3