Fair Share

অ্যালিস ও বব একটি $N$ সাইজের ইন্টিজার অ্যারে $A$ এর উপর একটি খেলা খেলছে। খেলাটি $K$ রাউন্ড ধরে চলে। প্রতিটি রাউন্ড নিচের মতো করে হয় -

1. অ্যালিস একটি ইন্টিজার X বাছাই করে যেখানে, $0 \leq X \leq$ অ্যারের কারেন্ট সাইজ।

2. বব হয় অ্যারের প্রথম X টি সংখ্যা মুছে দেয় অথবা বাকি সংখ্যাগুলো মুছে দিয়ে প্রথম X টি সংখ্যা রেখে দেয়।

এখন অ্যালিস চায় খেলা শেষে অ্যারেতে সংখ্যাগুলোর যোগফল যেন কম হয় এবং বব চায় যোগফল যেন বেশি হয়। যদি তারা উভয়ই সঠিকভাবে খেলে, তাহলে সেই যোগফল কত হবে ?

খেয়াল করো, খেলার মাঝে অ্যারেটি খালিও হতে পারে এবং একটি খালি অ্যারের সংখাগুলোর যোগফল 0।

Input

তোমাকে অনেকগুলো স্বতন্ত্র টেস্টকেস নিয়ে কাজ করতে হবে। প্রথম লাইনে টেস্টকেস সংখ্যা একটি ধনাত্বক পূর্ণসংখ্যা $T$ দেওয়া হবে।

প্রত্যেক টেস্টকেসের শুরুতে একটি লাইনে একটি ধনাত্বক পূর্ণসংখ্যা $N$ দেওয়া হবে, যা হল $A$ এ উপাদান এর সংখ্যা। তারপরের লাইনে $N$ সংখ্যক পূর্ণসংখ্যা $A_1, A_2, \dots, A_N$ দেওয়া হবে, সংখ্যাগুলোর মাঝে স্পেস থাকবে।

Constraints

$1 \leq T \leq 1000$
$1 \leq A_i \leq 10^9$

Subtask 1 (16 points)

$1 \leq N \leq 10^5$
$K = 64$
সব টেস্টকেস মিলিয়ে $N$ এর যোগফল $10^6$ এর বেশি নয়।

Subtask 2 (32 points)

$1 \leq N, K \leq 10^3$
সব টেস্টকেস মিলিয়ে $N$ এর যোগফল $10^4$ এর বেশি নয়।

Subtask 3 (52 points)

$1 \leq N, K \leq 10^5$
সব টেস্টকেস মিলিয়ে $N$ এর যোগফল $10^6$ এর বেশি নয়।

Output

প্রত্যেক টেস্টকেসের জন্য একটি লাইনে খেলা শেষে অ্যারেতে থাকা সংখ্যাগুলোর যোগফল আউটপুট দিবে। বিস্তারিত বোঝার জন্য স্যাম্পল দেখো।

Sample

Input	Output
3 5 1 1 2 3 4 5 5 2 1 2 3 4 5 5 3 1 2 3 4 5	9 5 5

প্রথম টেস্টকেসের ক্ষেত্রে,
প্রথম রাউন্ডঃ
অ্যালিস বাছাই করে $X = 3$
বব অ্যারের প্রথম $X$ টি সংখ্যা মুছে দেয় এবং বাকি থাকা সংখ্যাগুলো হলঃ $[4, 5]$

খেলা শেষে আরেতে থাকা সংখ্যাগুলোর যোগফল $= 4+5 = 9$

তৃতীয় টেস্টকেসের ক্ষেত্রে,
প্রথম রাউন্ডঃ
অ্যালিস বাছাই করে $X = 1$
বব অ্যারের প্রথম $X$ টি সংখ্যা মুছে দেয় এবং বাকি থাকা সংখ্যাগুলো হলঃ $[2,3,4,5]$

দ্বিতীয় রাউন্ডঃ
অ্যালিস বাছাই করে $X = 3$
বব প্রথম $X$ টি সংখ্যা রেখে দেয় এবং বাকি সংখ্যাগুলো মুছে দেয়।
বাকি থাকা সংখ্যাগুলো হলঃ $[2,3,4]$

তৃতীয় রাউন্ডঃ
অ্যালিস বাছাই করে $X = 2$
বব প্রথম $X$ টি সংখ্যা রেখে দেয় এবং বাকি সংখ্যাগুলো মুছে দেয়।
বাকি থাকা সংখ্যাগুলো হলঃ $[2,3]$

খেলা শেষে আরেতে থাকা সংখ্যাগুলোর যোগফল $= 2+3 = 5$