TianWang`ın Oyunu#4253
Əgər WHU ACM Komandası haqqında məlumatınız varsa, yəqin ki, bizim TianWang-ı tanıyırsınız və onun toxunulmaz istedadını və qabiliyyətini, xüsusilə oyun nəzəriyyəsində.
Bu oyun problemi də ondan gəlir. Qorxdunuz? Aha, cəsarətlə irəliləyin.
İki oyunçu bu oyunu 2·N tam ədədlə növbə ilə oynayır. Hər turda oyunçu bir tam ədədi götürə bilər, bu şəkildə hər bir oyunçunun sonunda N tam ədədi olur. Hər iki tam ədədin ƏBOBu (Ən Böyük Ortak Bölən) var, beləliklə oyunçunun tam ədəd cütləri olur; bütün cütlərin ƏBOBunun cəmi onun xalını təşkil edir. Oyunçuların məqsədi öz xalının rəqibinin xalı ilə fərqini maksimuma çatdırmaqdır.
Bu dəfə, kimin qalib gələcəyini bilmək istəmirik, çünki bu çox köhnədir; hər iki oyunçu ən yaxşı strategiyanı istifadə edərsə, onların xalları arasındakı son fərqi bilmək istəyirik.
Birinci sətir test halların sayını göstərən tək tam ədəd T ehtiva edir. Hər test halı bir tam ədəd N (1 ≤ N ≤ 1000) ilə başlayır, bu oyunçular üçün 2·N tam ədəd olduğunu göstərir. Sonra 2·N tam ədəd A_i (1 ≤ A_i ≤ 1000000) gəlir, bu tam ədədləri göstərir.
Hər hal üçün, iki oyunçunun xalları arasındakı son fərqi göstərən bir tam ədəd çıxarın.
Nümunə 1