AlgoLiga 2018

Bitriusz wziął udział w corocznej konferencji dot. matematyki zaawansowanej. Poruszanym tematem była wielowymiarowość w praktyce. Po zakończeniu wszystkich wykładów Bitriusz nie mógł przestać myśleć o wymiarach. Wszystko co widział, kojarzył z przestrzenią wielowymiarową. Gdy rozwiązał mu się but, zamiast go zawiązać zaczął się zastanawiać jakie hiperprostokąty udałoby mu się zbudować z długości powstałych po pocięciu owej sznurówki. Skacząc od jednej myśli do drugiej, zorientował się, że nie wie jak podzielić ową sznurówkę na kawałki o długościach będących liczbami naturalnymi, by zmaksymalizować objętość k-wymiarowego prostokątu powstałego z nich. Np. sznurówki o długości 10 cm można nie ciąć i otrzymać k-objętość równą 10 cm. Można ją też podzielić na 2 części po 5 cm. Mamy wtedy 2-wymiarowy prostokąt o k-objętości wynoszącej 25 cm² (jednostki nas nie interesują, liczy się wyłącznie wartość). Wydaje się, że jest to maksimum, które możemy osiągnąć. A może w 3 wymiarach otrzymalibyśmy więcej? Owszem! 3*3*4 daje nam 36 cm³ i jest to maksymalna wartość k-objętości. Bitriusz myślał i myślał, i nie udało mu się stworzyć algorytmu, który by optymalnie dzielił jego sznurówki. Może Tobie się uda.

Wejście

W pierwszej linii znajduje się liczba testów t (0 < t ≤ 100). Każdy test składa się z jednej linii zawierającej liczbę n (1 ≤ n ≤ 10⁹) oznaczającej długość sznurówki Bitriusza.

Wyjście

Dla każdego testu należy wypisać maksymalną k-objętość hiperprostokątu jaką da się uzyskać poprzez pocięcie sznurówki na dowolną ilość kawałków. Wynik należy podać modulo 1010101.

Przykład

Wejście:
2
10
7

Wyjście:
36
12