আর্ন্তজাতিক মাতৃভাষা দি‌বস প্রোগ্রামিং প্রতিযোগিতা

অনেক অনেক আশা এবং শত কোটি মানুষের ভালবাসা নিয়ে বাংলাদেশ ক্রিকেট দল এখন অস্ট্রেলিয়াতে। কোটি কোটি বাঙ্গালি এখন ক্রিকেট বিশ্বকাপ ২০১৫ এ তাদের সাফল্যের প্রতীক্ষায় উন্মুখ হয়ে বসে আছে। কিন্তু ক্রিকেট ম্যান্যাজমেন্ট বসে নেই, তাদের লক্ষ্য পরের বিশ্বকাপ। তাই এখন থেকেই তারা নতুন দল গড়ে তুলার প্রচেষ্টা শুরু  করে দিয়েছে। ইতোমধ্যে ২২ জন সম্ভাবনাময় খেলোয়াড়কে বেছে নিয়েছে পরের বিশ্বকাপের জন্য। এই ২২ জনকে নিয়ে দুটি দল গঠন করা হবে, আর তাদের মধ্যে হবে একটি ম্যাচ। এই ম্যাচই সহজ করে দেবে তাদের জাতীয় দলে স্থান পাওয়ার পথ।

২২ জন খেলোয়াড় থেকে ২টি দল গঠনের এই গুরুত্বপূর্ণ দায়িত্ব দেয়া হয়েছে আপনাকে। আর আপনার কাজকে সহজ করার জন্য প্রত্যেক খেলোয়াড়ের দক্ষতা সূচকও আপনাকে দেয়া হয়েছে। প্রত্যেক খেলোয়াড়ের সাম্প্রতিক রান, উইকেট, ক্যাচ, ফিল্ডিং এর ভিত্তিতে এই দক্ষতা সূচক নির্ধারণ করা হয়েছে, যা ১ থেকে ১০০০০০০ এর মধ্যে একটি পূর্ণ সংখ্যা। আপনার দায়িত্ব হচ্ছে এই ২২ জন খেলোয়াড়কে এমন ভাবে ২ টি দলে ভাগ করা জেন ২ টি দলের সম্মিলিত দক্ষতা সূচকের পার্থক্য সর্বনিম্ন হয়।

Input 

The first line of input indicates number of the test cases, T, where T ≤ 50. For every case there is one line of input which contains 22 space separated integers. Each integer represents the performance index, Pi, of each of 22 players. Each performance index is an integer between 1 and 1000000. So, we have the restriction 1 ≤ Pi ≤ 1000000.

Output 

For each test case divide the 22 players in to two teams such that their total performance indices are as close as possible. Then print the difference between the two sums on each line for each test case.

Sample Input 

3
100 109 121 100 99 96 99 75 102 110 101 112 96 96 91 64 112 113 139 121 80 133

550525 699235 355023 838444 697200 610547 753208 465348 748062 177696 521990 19899 583836 334620 504209 157498 103221 312702 742677 708756 14381 216701

100 200 300 400 500 600 700 800 900 1000 1100 10000 20000 30000 40000 50000 60000 70000 80000 90000 10000 11000

Sample Output 

1
2
4400

Problem Setter: Md Imrul Hasan