湯姆是個喜愛美好事物的少年，對各種事物都有美好的理想。
有一天他在逛街，街上有許多商家。本於追求完美的個性，湯姆希望到所有商家的距離總和加起來越小越好。
他把街道對應到一條線上，商家的位置用座標表示。但由於他最近忙著上網找資料作作業，所以想要請你幫他完成這小小地願望。你能為喜愛完美的湯姆，算出這個值嗎？
輸入第一行為一個正整數 t (t £ 30)，代表接下來有幾組測試資料。接下來每組第一行為一個正整數 n (n £ 1,000,000)，表示街道上有幾個商家。第二行有 n 個整數表示各個商家的所在位置。
每組測試資料輸出一個數字，表示最佳的位置。如果位置不只有一個，則輸出最小的那個。