Kapitan Mambeks z okazji swoich urodzin postanowił wydać wielkie przyjęcie. Na przyjęciu oczywiście nie może zabraknąć tortu urodzinowego. Kapitan tradycyjnie chciał być oryginalny więc zamówił tort w kształcie wielokąta foremnego (złożonego z N kątów/wierzchołków). Tort przyozdobiony jest N różnymi świeczkami, które rozmieszczone zostały w wierzchołkach tortu, przy czym w każdym wierzchołku jest tylko jedna świeczka. Rozcinając tort prostym cięciem od świeczki do świeczki można go podzielić na N-2 trójkątów. W zależności od tego pomiędzy którymi świeczkami tort jest rozcinany, można go podzielić na kilka sposobów. Przykładowo, jeżeli tort ma kształt pięciokąta (N = 5), to może być on podzielony na 3 trójkąty. Wszystkie możliwe sposoby podziału przedstawia poniższy rysunek:
Twoim zadaniem jest napisanie programu, który dla zadanej liczby sposobów podziału tortu, wyznaczy z ilu wierzchołków się on składa. Jeżeli istnieje kilka tortów dających się podzielić w taki sposób, to należy wybrać ten, który złożony jest z jak najmniejszej liczby wierzchołków.
W pierwszym wierszu znajduje się liczba M, będąca liczbą zestawów danych wejściowych. Pojedynczy zestaw danych składa się z jednego wiersza zawierającego liczbę całkowitą K (2 ≤ K ≤ 2.000.000.000) określającą liczbę sposobów podziału tortu.
Dane wyjściowe zawierają M wierszy. Jeden wiersz odpowiada jednemu zestawowi danych wejściowych i zawiera liczbę naturalną będącą liczbą wierzchołków tortu.
5 2 4 7 12 22
4 5 6 6 7