Dãy số Lucas là dãy số thỏa mãn điều kiện: $$L[1] = 1, L[2] = 3, L[i] = L[i-1] + L[i-2] \forall i \ge 3.$$ Các phần tử đầu tiên của dãy Lucas là 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...

Tổng Nim của hai số nguyên không âm là kết quả phép cộng không nhớ của hai số đó trong hệ cơ số 2. Ví dụ:

• Số 18 viết dưới dạng cơ số 2 là: 10010_2.
• Số 29 viết dưới dạng cơ số 2 là: 11101_2.
• Tổng Nim của chúng là: 01111_2 (là số 15 trong hệ thập phân).

Trong các dãy con liên tiếp của dãy Lucas có chỉ số thuộc đoạn ~[x, y]~, hãy tìm dãy con có tổng Nim lớn nhất và cặp ~(x, y)~ thỏa mãn điều kiện: $$ \begin{cases} (y^{x+1} + (y+1)^x) \text{ chia hết cho } x^2 \\ x, y \text{ là các số nguyên dương} \\ x < y \le N \end{cases} $$

Yêu cầu: Hãy giúp tìm tổng Nim lớn nhất tìm được ứng với mỗi bộ dữ liệu vào.

Input

• Dòng 1: Ghi số nguyên dương ~T~ là số bộ dữ liệu (~T \le 10^6~).
• ~T~ dòng tiếp theo, mỗi dòng ghi số nguyên dương ~N~ là số phần tử của dãy Lucas (~2 \le N \le 88~).

Output

• Gồm ~T~ dòng, mỗi dòng ghi tổng Nim lớn nhất tìm được tương ứng với bộ dữ liệu đầu vào.

Sample Input 1

2
68
82

Sample Output 1

96046080412173
7288082074054989

Subtasks