题目描述

对于一个非负整数K，求出K的所有拆分中回文的拆分个数。

例如：4 = 1+1+1+1 = 1+1+2 = 1+2+1 = 2+1+1 = 2+2 = 1+3 = 3+1

其中回文的拆分有1+1+1+1,1+2+1,2+2 共3种（所谓拆分，也就是必须要拆，不拆不算拆分）

输入格式

一个非负整数K（0≤K≤99）

输出格式

一个正整数，表示K的回文拆分总个数

样例

输入样例#1：

4

输出样例#1：

3