Doubloon Oyunu#3129
Qəpir olmaq çox vaxtı dənizdə keçirmək deməkdir. Bəzən, külək olmadıqda, günlər heç bir fəaliyyət olmadan keçə bilər. Təmir işləri arasında vaxt keçirmək üçün qəpirlar sikkələrlə oyunlar oynamağı sevirlər.
Qəpirlar arasında klassik favorit oyun iki oyunçu arasında bir sikkə yığını ilə keçirilən oyundur. Növbə ilə, hər oyunçu yığından müəyyən sayda sikkə götürür. Oyunçunun götürdüyü sikkə sayı verilmiş tam ədədinin qüvvəti olmalıdır (, , K^2 və s.). Oyunun qalibi son sikkə(ləri) götürən oyunçudur.
Qəpirların mövcud oyun vəziyyətində növbəti oyunçunun qalib ola biləcəyini necə müəyyən edəcəyinə kömək edə bilərsinizmi?
Birinci sətirdə testlərin sayı verilir.
Hər bir test üçün aşağıdakılar verilir:
Bir sətirdə iki tam ədəd və (1 \leq S \leq 10^9, 1 \leq K \leq 100) — yığının ölçüsü və parametr .
Hər test üçün cavabı ayrıca sətirdə çap edin: qalibiyyəti təmin edən minimum sikkə sayını. Əgər belə bir variant yoxdursa, **0** yazın.
Nümunə 1