100000004 - largest palindrome product

Time Limit

10 毫秒

Memory Limit

128 MB

通过次数

3

提交次数

5

寻找两个三位数乘积中最大的回文数。

例如,两个二位数乘积中最大的回文数为9009,即91与99的乘积。

Input

Output

Examples

Input


                            

Output


                            

Hint

偶数位回文数都是11的倍数,例如6位回文数,设回文数为abccba,则有:abccba=11(9091a+910b+100c)。

更通用的讲,回文数问题多可以用构造回文数的方法来优化。而偶数位回文数具有特殊性质:一定为11的倍数。

另外,有趣的是,通过数学方法反转一个数字,并不比比通过stringstream将其转换为string后反转(通过swap函数和双指针)再通过stringstream将其转化回数字快。