תיאור

"עבור בעיות שאינכם יודעים כיצד לפתור, פשוט הגישו משהו אקראי. מי יודע, אולי זה יעבור."

נתונה מטריצת מספרים בגודל $n \times m$. באפשרותכם לסדר מחדש באופן שרירותי את המספרים בכל שורה כך שסכום הערכים המינימליים של כל העמודות יהיה מרבי.

באופן פורמלי, תהי המטריצה המסודרת מחדש $A$. מקסמו את $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$.

עליכם להדפיס ערך מרבי זה.

"לעיתים קרובות, העובדה שדברים מתנהלים בניגוד לרצוננו היא פשוט הנורמה בחיים."

קלט

השורה הראשונה של הקלט מכילה את מספר מקרי הבדיקה $T$ ($1 \leq T \leq 10^5$).

עבור כל מקרה בדיקה, השורה הראשונה מכילה שני מספרים שלמים חיוביים $n, m$ ($1 \leq n, m \leq 1000$), המייצגים את גודל המטריצה.

$n$ השורות הבאות מכילות כל אחת $m$ מספרים שלמים, המייצגים את המספרים $A_{i,j}$ במטריצה ($0 \leq A_{i,j} \leq 10^9$).

מובטח שסכום $n \cdot m$ על פני כל מקרי הבדיקה אינו עולה על $10^6$.

פלט

עבור כל מקרה בדיקה, הדפיסו מספר שלם בודד בשורה אחת המייצג את התשובה.

דוגמאות

קלט 1

3
1 1
5
2 2
1 4
2 5
3 3
1 2 1
2 2 1
1 1 2

פלט 1

5
5
4