Super Xəsis#3715
İki nəfər "Acgöz" oyununu oynayır. n ədəd a_i konfetdən ibarət yığın var. İki oyunçu növbə ilə hər hansı bir yığından 1 ilə k arasında istənilən sayda konfet götürə bilər. Hər hansı bir yığından sonuncu konfet götürən şəxs uduzur. Hər iki oyunçu düzgün oynadıqda, birinci oyunçunun qalib gəlməsi üçün ilk gedişi neçə üsulla edə biləcəyini tapın.
Birinci sətirdə oyunların sayı t (1 ≤ t ≤ 10^5) verilir. Növbəti t sətirdə oyunların təsviri verilir: n (1 ≤ n ≤ 10^5), k (1 ≤ k ≤ 10^9) və n ədəd a_i (1 ≤ a_i ≤ 10^9).
Bütün oyunlarda yığınların ümumi sayı 10^5-dən çox deyil.
Hər oyun üçün, hər iki oyunçu düzgün oynadıqda, birinci oyunçunun qalib gəlməsi üçün ilk gedişi neçə üsulla edə biləcəyini çıxarın. Əgər birinci oyunçu uduzursa, 0 çıxarın.
Nümunə 1