Недавно в Берляндии начал проводится спортивный турнир по k видам спорта. А Вася хочет подзаработать на ставках.
Схема турнира весьма загадочна и полностью не раскрывается. Состязания проходят последовательно, в каждом их них участвуют два спортсмена, которые ещё не вылетели из турнира. Каждое состязание может проходить в любом из k видов спорта. Проигравший спортсмен вылетает из турнира. Последний оставшийся спортсмен становится победителем турнира. В остальном схема может быть произвольной, заранее она не разглашается.
Васе известны способности спортсменов к разным видам спорта. Он считает, что более способный спортсмен всегда победит менее способного.
Турнир проводится каждый год, и каждый раз к нему присоединяется один новый спортсмен. В первом турнире участвовал лишь один спортсмен, во втором – два, и так далее. Вася следит за турниром в течение n лет. Помогите ему для каждого из n турниров узнать, сколько существует претендентов на победу в турнире.
Выходные данные
Для каждого из n турниров выведите количество возможных победителей.
Примечание
В первом примере:
В первом турнире участвует один спортсмен, он и является победителем.
Во втором турнире два спортсмена, каждый из которых может обыграть другого, в зависимости от вида спорта.
В третьем турнире третий игрок побеждает любого в любом виде спорта, и он победит при любой схеме.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 5
5 1
10 10
|
1
2
1
|
|
2
|
3 2
2 2
3 3
1 10
|
1
1
3
|
|
3
|
3 2
2 3
1 1
3 2
|
1
1
2
|