Аня пришла на день рождения к своей подруге. На столе по кругу распложено \(n\) вкуснейших сладостей (для удобства пронумеруем их от \(1\) до \(n\) по часовой стрелке). Для каждой из сладостей известно, нравится она Ане или нет. Аня решила, что она должна съесть все сладости, которые есть на столе и нравятся ей.
Однако, есть все сладости подряд слишком скучно. Поэтому Аня придумала игру, которая позволит сделать процесс поедания сладостей более интересным.
Игра проходит по следующим правилам:
- если на столе не осталось сладостей, которые нравятся Ане, то игра заканчивается;
- в самом начале игры, если на столе есть хотя бы одна сладость, которую Аня хочет съесть, она съедает сладость под номером \(1\);
- после того, как Аня съела какую-то сладость, она отсчитывает \(k\) сладостей по часовой стрелке, начиная со следующей сладости в круге, и съедает \(k\)-ю сладость в отсчете (если в круге меньше \(k\) сладостей, некоторые сладости могут поучаствовать в отсчете несколько раз, и Аня выбирает последнюю сладость в отсчете). Очевидно, уже съеденные сладости в отсчете не участвуют.
Например, пусть по кругу расположены \(6\) сладостей, сладости под номерами \(4\), \(5\) и \(6\) нравятся Ане, \(k = 4\). Тогда игра проходит следующим образом:
- изначально на столе расположены сладости \([1, 2, 3, 4, 5, 6]\), Аня выбирает сладость под номером \(1\).
- Аня съедает сладость \(1\), после этого на столе остаются сладости \([2, 3, 4, 5, 6]\). Аня отсчитывает \(4\) сладости, начиная со сладости \(2\), и останавливается на сладости \(5\).
- Аня съедает сладость \(5\), после этого на столе остаются сладости \([2, 3, 4, 6]\). Аня отсчитывает \(4\) сладости, начиная со сладости \(6\), и останавливается на сладости \(4\).
- Аня съедает сладость \(4\), после этого на столе остаются сладости \([2, 3, 6]\). Аня отсчитывает \(4\) сладости, начиная со сладости \(6\), и останавливается на сладости \(6\).
- Аня съедает сладость \(6\), после этого на столе остаются сладости \([2, 3]\). На столе не осталось сладостей, которые нравятся Ане, поэтому игра заканчивается.
Ваша задача — определить, сколько сладостей съест Аня.