Манао пытается взломать очень любопытный замок. На замке есть n кнопок, которые нужно нажать в определенной последовательности, чтобы открыть его. Когда происходит нажатие на какую-либо кнопку, она либо остается зажатой, что означает, что она действительно является следующей в последовательности, либо она сбрасывается вместе со всеми зажатыми в данный момент кнопками. Когда одновременно оказываются зажаты все кнопки, замок открывается.
Рассмотрим пример с тремя кнопками. Скажем, последовательность нажатия кнопок, открывающая замок, равна: {2, 3, 1}. Если сначала нажать на кнопки 1 или 3, они немедленно сбросятся. Если нажать на кнопку 2, она останется зажатой. Если после нажатия кнопки 2 нажать на кнопку 1, то все кнопки сбросятся. Если же после нажатия кнопки 2 нажать на кнопку 3 — она останется зажатой вместе с кнопкой 2. При двух зажатых кнопках остается лишь нажать на кнопку 1, чтобы замок открылся.
Манао не знает последовательность, в которой нужно нажимать кнопки, чтобы открыть замок. Зато он очень умный и будет действовать оптимально. Вычислите количество нажатий, которое ему придется произвести для открытия замка в худшем случае.
Примечание
Рассмотрим первый тестовый пример. Манао может не повезти с первым нажатием и он нажмет не на ту кнопку, на которую надо было нажимать первой. В таком случае вторым ходом он уже может отгадать первую кнопку. А третьим — вторую кнопку. Таким образом, в худшем случае ему понадобится всего 3 нажатия.