المجاميع الجميلة هي مجاميع عدة أعداد صحيحة موجبة متتالية. على سبيل المثال، المجموعان $7 + 8$ و$4 + 5 + 6$ جميلان، أما المجموع $3 + 5 + 7$ فليس جميلاً، رغم أن القيمة في جميع الحالات تساوي $15$. (يُعد المجموع ذو الحد الوحيد $15$ جميلاً أيضاً.)

بناءً على ذلك، مؤشر جمال عدد صحيح هو عدد طرق تمثيله كمجموع جميل. على سبيل المثال، مؤشر جمال العدد $15$ يساوي $4$، إذ يمكن تمثيل $15$ كمجموع جميل بأربع طرق: $15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5$.

يكون عدد أجمل من عدد آخر إذا كان مؤشر جماله أعلى. وإذا تساوى مؤشرا الجمال، يُعد العدد الأصغر أجمل. على سبيل المثال، $15$ هو أصغر عدد صحيح مؤشر جماله $4$.

عليك إيجاد أصغر عدد صحيح له مؤشر الجمال المعطى $n$.

الإدخال

يحتوي سطر واحد على عدد صحيح $n$ ($1 \le n \le 10^5$).

الإخراج

اطبع أصغر عدد صحيح له مؤشر الجمال المعطى $n$، بترديد $(10^9 + 9)$.

أمثلة

الإدخال 1

3

الإخراج 1

9

الإدخال 2

4

الإخراج 2

15