Description

对于一个非负整数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种（所谓拆分，也就是必须要拆，不拆不算拆分）

Format

Input

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

Output

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

Samples

4

3

Limitation

1s, 1024KiB for each test case.