На выставке змей есть \(n\) комнат (пронумерованных от \(0\) до \(n - 1\)) расположенных по кругу. В каждой комнате находится одна змея. Комнаты соединены \(n\) конвейерами, \(i\)-й из них соединяет комнаты \(i\) и \((i+1) \bmod n\). Другими словами, комнаты \(0\) и \(1\), \(1\) и \(2\), \(\ldots\), \(n-2\) и \(n-1\), \(n-1\) и \(0\) соединены конвейерами.
Конвейер \(i\) может быть в одном из трех состояний:
- Если он направлен по часовой стрелке, змеи могут проползти только из комнаты \(i\) в \((i+1) \bmod n\).
- Если он направлен против часовой стрелки, змеи могут пройти только из комнаты \((i+1) \bmod n\) в \(i\).
- Если он выключен, змеи могут проползти в обоих направлениях.
В этом примере \(4\) комнаты, где конвейеры \(0\) и \(3\) выключены, конвейер \(1\) направлен по часовой стрелке, а конвейер \(2\) — против часовой стрелки.
Каждая змея хочет покинуть свою комнату, поползать и вернуться в нее потом снова. Назовем комнату возвратимой, если змея может покинуть ее и вернуться в нее позже, ползая по конвейерам. Сколько всего возвратимых комнат?
Выходные данные
Для каждого набора входных данных выведите количество возвратимых комнат.
Примечание
В первом наборе входных данных все комнаты являются возвратимыми, кроме комнаты \(2\). Змея в комнате \(2\) заблокирована и не может выйти. Этот набор входных данных соответствует картинке из условия задачи.
Во втором наборе входных данных все комнаты являются возвратимыми, потому что можно вернуться в любую комнату, несколько раз пройдя по конвейерам, направленным по часовой стрелке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
-><-
5
>>>>>
3
<--
2
<>
|
3
5
3
0
|