当前没有测试数据。

题目描述

聪聪可被明明出的题目难倒了好一会，不过，经过一番思考，聪聪还是把它解决了。作为回报，聪聪也给明明出了一个问题：平方数，或称完全平方数，是指可以写成某个整数的平方的数，即其平方根为整数的数。例如，9 = 3 × 3，它是一个平方数。聪聪很早就发现4=2×2,9=3×3……。而2不可能分解为两个整数的乘积，但可以分解为1×1+1×1。聪聪曾经遇到过对于任意给定的正整数n把它分解成几个自然数的和的问题，在了解了平方数的知识后，聪聪想知道在所有拆分方案中，满足所有加数都是平方数的方案有多少？

输入格式

一个正整数n。

输出格式

满足条件的方案数。

样例

输入#1

5

输出#1

2

解释#1

5有2种分解方案，它们是：5=1×1+1×1+1×1+1×1+1×1=1×1+2×2

输入#2

13

输出#2

6

解释#2

13有6种分解方案，它们是： 13=1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1 =1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+2×2 =1×1+1×1+1×1+1×1+1×1+2×2+2×2 =1×1+1×1+1×1+1×1+3×3 =1×1+2×2+2×2+2×2 =2×2+3×3

数据范围

• 20%的数据，1≤n≤10;
• 50%的数据，1≤n≤50;
• 80%的数据，1≤n≤800;
• 100%的数据，1≤n≤2000。