Испокон веков разделением учеников на факультеты занимается волшебная шляпа. Раньше в школе было четыре различных факультета, но после недавних реформ факультетов стало \(p\). Шляпа же всё ещё занимается распределением учеников.

Перед торжественной церемонией шляпа заранее составляет план распределения учеников по факультетам. План является последовательностью чисел \(a_1, a_2, \ldots, a_k\), где \(a_i\) является номером факультета, на который попадет \(i\)-й ученик.

В своём плане шляпа использует для факультетов номера от \(0\) до \(p-1\). Следующим за \(i\)-м факультетом считается \((i+1)\)-й, за \((p-1)\)-м - нулевой. Первая версия плана содержит только один факультет - нулевой. После чего шляпа много раз дописывает в конец плана текущее содержимое плана, заменив каждый факультет на следующий.

Рассмотрим распределение девяти учеников по четырём факультетам. Шляпа будет последовательно строить следующие планы: \((0)\), \((0, 1)\), \((0, 1, 1, 2)\), \((0, 1, 1, 2, 1, 2, 2, 3)\), \((0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 0)\). Длина последнего плана достаточна для распределения всех учеников по факультетам, поэтому следующие планы шляпа может не строить.

Скажите, на какой из \(p\) факультетов шляпа распределит \(n\)-го ученика.

10
1 1000
2 1000
4 1000
8 1000
16 1000
32 1000
64 1000
128 1000
256 1000
512 1000

0
1
2
3
4
5
6
7
8
9