После празднования дня рождения Тимофей пошел на свою любимую березовую аллею, чтобы покормить своих любимых птиц — ворон. Вороны уже привыкли к маленькому Тимофею, поскольку он очень добрый и заботливый мальчик — постоянно подкармливает своих любимцев.
Как известно, на каждой березе живет ровно одно семейство ворон. Березы в аллее стоят в ряд и пронумерованы от 1 до n. Также известно, что некоторые семейства дружат между собой. По некоторым причинам одно семейство может дружить с другим, только если они живут на достаточно близком расстоянии, а именно, между любыми двумя дружащими семействами должна быть не более чем k - 1 береза. Более формально, семейство, живущее на дереве u, может дружить с семейством, живущим на дереве v, только если |u - v| ≤ k.
Одно из проявлений дружбы заключается в том, что если некоторое семейство узнает, что Тимофей где-то кормит ворон, то оно немедленно сообщит об этом всем семействам, с которыми оно дружит. Таким образом, после того, как Тимофей начнет кормить ворон около некоторой березы, к месту кормежки слетятся все семейства, которые дружат с семейством, живущим на этой березе, непосредственно или через цепочку нескольких дружественных отношений. Разумеется, обитатели данной березы тоже слетятся.
Сегодня Тимофей пришел на аллею, и обнаружил, что все семейства, живущие на березах с номерами, строго меньшими l или строго большими r, куда-то улетели. Таким образом, передача информации о кормежке через них невозможна. Кроме того, кормить их также не нужно. Помогите Тимофею узнать, возле какого минимального числа берез Тимофею необходимо покормить ворон, чтобы все оставшиеся семейства узнали о кормежке. Вам дано несколько возможных ситуаций, определяемых числами l и r, и требуется посчитать ответ для каждой из них.