Little09 и его друзья играют в игру. Есть \(n\) игроков, и значение температуры игрока \(i\) равно \(i\).
Типы окружающей среды обозначаются как \(0\) или \(1\). Когда два игрока сражаются в определенной среде, если её тип равен \(0\), то всегда побеждает игрок с более низким значением температуры; если он равен \(1\), то всегда побеждает игрок с более высоким значением температуры. Типы этих сред \(n-1\) образуют бинарную строку \(s\) длиной \(n-1\).
Если в игре участвует \(x\) игроков, то всего будет \(x-1\) сражений, а типами \(x-1\) сред будут первые \(x-1\) символов \(s\). Если в турнире осталось более одного игрока, выберите для сражения любых двух оставшихся игроков. Игрок, который проиграет, выбывает из турнира. Типом среды для \(i\)-го сражения является \(s_i\).
Для каждого \(x\) от \(2\) до \(n\) ответьте на следующий вопрос: если в игре участвуют все игроки, значение температуры которых не превышает \(x\), то сколько игроков имеют шансы на победу?
Примечание
В первом наборе входных данных для \(x=2\) и \(x=3\) победителем может стать только игрок, чье значение температуры равно \(1\). Для \(x=4\) победителем могут стать игроки, чьи значения температуры равны \(2,3,4\).