Определение. Если число 2^N−1 простое, то оно называется простым числом Мерсенна.

Например, 2²−1 — первое простое число Мерсенна, 2³−1 — второе, 2¹¹²¹³−1 — 23-e, 2²¹⁶⁰⁹¹−1 — 31-e.

Искать эти числа без компьютера довольно тяжело. Так, Эйлер в 1772 году нашёл 8-е число, 2³¹−1, но после этого в течение 100 лет не было найдено ни одного! Лишь в 1876 Люк показал, что 2¹²⁷−1 — простое число. Но он нашел не 9-е, а сразу 12-е, так как 2⁶¹−1, 2⁸⁹−1, 2¹⁰⁷−1 — тоже простые, но были найдены позднее. Новый прорыв случился лишь в 1950-х, когда с помощью вычислительной техники были найдены простые числа Мерсенна с показателями 521, 607, 1279, 2203, 2281. Все последующие числа Мерсенна были найдены с помощью ЭВМ. И для этого не нужно было быть великим математиком, в 1978 и 1979 годах студенты Нолл и Никел нашли 25-е и 26-е числа (21701 и 23209) на мэйнфрейме своего университета, чем и прославились на всю Америку. Но и у современных суперкомпьютеров есть пределы возможностей. Сегодня простые числа Мерсенна ищут десятки тысяч людей по всему миру, объединённые одним метапроектом GIMPS (Great Internet Mersenne Prime Search, www.mersenne.org). На счету GIMPS уже 8 самых больших простых чисел Мерсенна. Их показатели — 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951. 2^6972593−1 является 38-м простым числом Мерсенна, а про последние 4 ещё нельзя сказать, какие они по счету, т.к. ещё не все меньшие числа проверены. Эти же 4 числа являются самыми большими известными простыми числами.

Последнее число — 2^25964951−1 — было найдено 18 февраля 2005 года, оно состоит из 7816230 десятичных цифр, тот же, кто найдёт простое число более чем из 10 миллионов цифр, получит приз в $100000. Эти деньги можете выиграть и Вы, если присоединитесь к проекту.

Сейчас от Вас, конечно, не требуется найти за 5 часов 43-е простое число Мерсенна, ведь жюри просто не сможет проверить Ваш ответ. В этой задаче N не превосходит 38. Итак, Вам даётся N, от Вас требуется найти N-е по порядку простое число Мерсенна.

В первой строке дано число T — количество тестов. В каждой из последующих T строк дано число N.

Для каждого числа N выведите показатель N-го по порядку простого числа Мерсенна.