Напомним, что простое число — это целое число, которое делится ровно на два целых числа: на единицу и на себя. Последовательность простых чисел начинается с \(2, 3, 5, \ldots\).
Рассмотрим первые \(n\) простых чисел. Давайте разделим их на две части \(A\) и \(B\) так, чтобы каждое простое число принадлежало ровно одной из этих двух частей. Обозначим произведение всех простых чисел в \(A\) как \(a\), а произведение всех простых чисел в \(B\) как \(b\). Произведение чисел в пустом множестве будем считать равным \(1\). Будем называть разбиение красивым, если \(a < b\) и \(b-a\) минимальное возможное.
Дано \(n\), найдите красивое разбиение множества первых \(n\) простых чисел и выведите соответствующее значение \(a\).
Формат входных данных
Входные данные содержит целое число \(n\) на отдельной строке (\(1 \le n \le 30\)).
Формат выходных данных
Выведите значение \(a\) в красивом разбиении множества первых \(n\) простых чисел.