ЛКШатский Дед Мороз решил приехать к нам на день раньше, чтобы увидеть, как вы решаете задачи Новогодней олимпиады 2014. Но, к сожалению, его ждут и в других Летних Зимних Школах. В частности, он обязательно должен побывать в Летней Физической Школе (ЛФШ.Зима), иначе их директор обидится на Деда Мороза и больше его не пригласит. Чтобы все же ему разрешили уехать к нам пораньше, Директор ЛКШ должен обыграть директора ЛФШ.Зима в игру, придуманную, как считают ЛФШата, специально для этого.
На столе перед директорами в кучке лежат N камней. Игроки по очереди делают ходы. На каждом ходе игрок может взять от 1 до K камней из кучки. Первым ходит Директор ЛКШ. Проигрывает тот, кто на своем ходе не сможет взять камень. Их Директор оказался достаточно умным и делает всегда оптимальные ходы. Но мы-то и поумнее видали. Для нескольких игр посчитайте, сколько из них выиграет Директор ЛКШ при правильной игре обоих.
В первой строке входного файла записано число 1 ≤ t ≤ 104 — количество игр. Далее в t строках записаны через пробел по два числа — N (1 ≤ N ≤ 109) и K (1 ≤ K ≤ 109) — описание очередной игры.
В выходной файл выведите количество игр, которые сможет выиграть наш любимый Директор.
5
3 2
3 3
7 4
9 2
212 77
3
После разгромной победы Директора ЛКШ руководитель физической школы сдался и отпустил Деда Мороза к нам. Но ради интереса предложил сразиться ЛФШатам и ЛКШатам в еще одной непростой игре.
В каждой игре участвует один из вас и один ЛФШонок, а ходите вы по очереди. В кучку перед вами кладется N вкусных конфеток. На каждом ходе игрок может съесть от 1 до K конфеток (больше нельзя — много сладкого вредно даже в Новый Год), но при этом не больше, чем взял его противник на предыдущем ходе (не будем жадничать, мы же добрые). Второго ограничения нет лишь для первого хода каждой игры. Проигрывает тот, кому не осталось конфеток.
У нас возникли подозрения, что директор ЛФШ специально подобрал такие N и K, чтобы ЛКШата никогда не смогли выиграть. Мы надеемся, что это не так, и очень просим вас проверить это.
Во входном файле записаны через пробел два целых числа — N (1 ≤ N ≤ 500) и K (1 ≤ K ≤ 100).
В выходной файл выведите число конфет, которое должен съесть ЛКШонок первым ходом, чтобы выиграть при оптимальной игре ЛФШонка, либо 0, если даже самый умный из нас не сможет одолеть идеального играющего противника.
7 3
3
Если в свой ход ЛФШонок берёт 2 или 3 конфетки, то следующим ходом вы можете закончить игру, если же он возьмёт одну конфетку, то далее каждый будет съедать по одной конфетке и последняя достанется вам.
Братья Аркадий и Борис играют в следующую игру. В ряд стоят n уникальных ваз эпохи Мин. За ход можно разбить либо крайнюю слева вазу, либо крайнюю справа вазу. У каждой вазы есть стоимость ai. Каждый из игроков хочет, чтобы суммарная стоимость разбитых им ваз была максимальна. Первым ходит Аркадий. Определите результат игры при оптимальной игре обоих игроков.
В первой строке входного файла задано число n (1 ≤ n ≤ 1000). В следующей строке задано n чисел ai (1 ≤ ai ≤ 1000).
Выведите в выходной файл два числа: суммарные стоимости ваз, разбитых Аркадием и Борисом, соответственно.
4
1 2 4 3
5 5