Xét tập số nguyên ~S~ được định nghĩa như sau:

• Số ~1~ thuộc ~S~;

• Nếu ~x~ thuộc ~S~, thì ~2x+1~ và ~3x+1~ cũng thuộc ~S~;

• Tập ~S~ được sắp xếp tăng dần, không chứa số nào khác ngoài các số theo quy tắc đã nêu và mỗi số xuất hiện một lần.

Các số đầu tiên của tập ~S~ vô hạn là: ~\{1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, 28, 31, 39, 40, 43, 45, 46, 55, 57, 58, 63, 64, 67, 79, 81, 82, 85, 87, 91, 93, 94, \dots\}~

John điền ~N^2~ phần tử đầu tiên của tập ~S~ vào một bảng gồm ~N~ hàng, ~N~ cột theo thứ tự từ trái sang phải, từ trên xuống dưới.

Yêu cầu: Hãy tìm hình vuông con có cạnh lớn nhất của bảng có tổng các phần tử cũng là một số thuộc tập ~S~.

Input

Ghi một số nguyên dương ~N~.

Output

Ghi ra cạnh của hình vuông con lớn nhất có tổng các phần tử cũng là một số thuộc tập ~S~.

Scoring

Sample Input 1

14

Sample Output 1

12

Notes

Với ~N = 14~, hình vuông cạnh ~K = 12~, tọa độ góc trái trên của hình vuông là ~(3, 1)~, có tổng các số trong hình vuông bằng ~73965~ là một số thuộc tập ~S~.