题目描述

把整数3025从中剪开分为30和25两个数，此时再将这两数之和平方，（30+25）^2=3025 计算结果又等于原数。 现在的任务是让你求出从小到大按顺序第k个符合这个条件的四位数。 最小的四位数是1000，最大的四位数是9999。

输入格式

一个整数 k 0<k<10

输出格式

从小到大按顺序第k个符合条件的数。

样例

input

1

output

2025

限制与提示

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$