Любимое занятие Маленького Чу — спать. Строго говоря, он только это и делает. Но иногда он просыпается, и тогда человечество делает какое-нибудь Великое Открытие. Первый раз Чу проснулся через K дней после рождения. Второй раз он проснулся через K² дней после рождения. Третий раз — через K³ дней. Эта закономерность сохраняется и поныне.

Каждый раз, когда Маленький Чу просыпается, он смотрит на календарь и запоминает, какой сегодня день недели. Говорят, что если день недели повторится, то он начнёт плакать, и его слёзы затопят весь мир.

Ваша задача — сделать наибольшее количество Великих Открытий и максимально оттянуть конец света. Определите, когда нужно разбудить Чу в первый раз, если известно, что сразу после рождения он не может спать больше недели.

Первая строка содержит число T (1 ≤ T ≤ 6553) — количество тестов. На каждой из следующих T строк находится число N (2 < N < 65536) — количество дней в неделе. N — простое.

Для каждого теста выведите на отдельной строке число K.