Cho dãy \(A\) gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) và một số nguyên dương \(k \le n\).

Yêu cầu: Hãy chọn ra trong dãy này đúng \(k\) phần tử sao cho tích của \(k\) phần tử này lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(1 \le T \le 10\)) — số lượng bộ dữ liệu (test case).
• Tiếp theo là \(T\) bộ dữ liệu, mỗi bộ gồm hai dòng:
  • Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(k\) (\(1 \le k \le n \le 10^5\)).
  • Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)).
• Tổng \(n\) trong tất cả các test case không vượt quá \(2 \cdot 10^5\).

Output

• Với mỗi test case, in ra trên một dòng phần dư của tích lớn nhất khi chia cho \(123456789\).

Example

3
5 3
1 2 3 4 5
6 4
-1 -1 -1 -1 0 9
5 3
-1 -1 -1 2 3

60
1
3