Инна очень любит сладкое. Перед ней в ряд лежат n закрытых подарочных коробочек. В каждой из этих коробочек либо лежит конфета (Дима постарался), либо ничего не лежит (Сережа постарался). Будем считать, что коробочки пронумерованы от 1 до n слева направо.

Так как коробочки закрыты, Инна не знает, в каких коробочках лежат конфеты, а в каких — нет. Для того, чтобы узнать это, Инна выбрала число k и задала w вопросов Диме. Каждый вопрос характеризуется двумя целыми числами l_i, r_i (1 ≤ l_i ≤ r_i ≤ n; r - l + 1 делится на k), i-ый вопрос: «Дима, правда, что среди коробочек с номерами от l_i до r_i включительно конфеты лежат исключительно в коробочках с номерами l_i + k - 1, l_i + 2k - 1, l_i + 3k - 1, ..., r_i?»

Дима очень не любит говорить Инне: «Нет!». Поэтому ему интересно, какое количество действий придется совершить для каждого вопроса, чтобы ответ на вопрос был положительным. За одно действие Дима может либо незаметно достать конфету из любой коробки, либо незаметно положить конфету в любую коробку (у Димы бесконечно много конфет). Помогите Диме, посчитать количество действий для каждого вопроса Инны.

Обратите внимание, что Дима не меняет массив во время вопросов Инны. Поэтому когда ведется подсчет количества операций для текущего вопроса, считается, что последовательность коробочек не изменялась.