Нина придумала новую игру, основанную на возрастающей последовательности целых чисел \(a_1, a_2, \ldots, a_k\).
В этой игре, изначально \(n\) игроков встают в ряд. В каждом раунде происходит следующее:
- Нина находит \(a_1\)-го, \(a_2\)-го, \(\ldots\), \(a_k\)-го игроков в ряду. Они покидают игру одновременно. Если игру должен покинуть \(i\)-й игрок в ряду, но в ряду меньше \(i\) игроков, этот игрок пропускается.
Как только в некотором раунде никто не покинул игру, все игроки, находящиеся в игре в данный момент, объявляются победителями.
Например, рассмотрим игру с \(a=[3, 5]\) и \(n=5\) игроками. Пусть игроков зовут игрок A, игрок B, \(\ldots\), игрок E в том порядке, в котором они выстроились изначально. Тогда,
- Перед первым раундом, порядок игроков в ряду ABCDE. Нина находит \(3\)-го и \(5\)-го игроков в ряду. Это игроки C и E. Они покидают игру в первом раунде.
- Теперь порядок игроков ABD. Нина находит \(3\)-го и \(5\)-го игроков в ряду. \(3\)-й игрок это игрок D и в ряду нет \(5\)-го игрока. Поэтому только игрок D покидает игру во втором раунде.
- В третьем раунде никто не покидает игру, поэтому после этого раунда игра заканчивается.
- Игроки A и B объявляются победителями.
Нина пока не решила, сколько игроков будут принимать участие в игре. Она даст вам \(q\) целых чисел \(n_1, n_2, \ldots, n_q\), а вы должны ответить на следующий вопрос для всех \(1 \le i \le q\) независимо:
- Сколько игроков будут объявлены победителями, если изначально в игре будут принимать участие \(n_i\) игроков?
Выходные данные
Для каждого набора входных данных выведите \(q\) целых чисел: \(i\)-е (\(1\le i \le q\)) из них должно быть равно количеству игроков, которые будут объявлены победителями, если изначально в игре будет принимать участие \(n_i\) игроков.
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе входных данных при \(n=1\), единственный игрок остаётся в игре после первого раунда. После этого, игра заканчивается и он объявляется победителем.