设f[i][j]表示深度为i，节点数为j的二叉树个数
g[i][j]表示深度不超过i，节点数位j的二叉树个数
那么可以列出dp方程
f[i][j]=sigma(f[i-1][k]*g[i-2][j-k-1]*2+f[i-1][k]*f[i-1][j-k-1]))
g[i][j]=g[i-1][j]+f[i][j]

那么在O(n^3)就可以预处理出所有的f[i][j]值
然后对于每个询问查表输出答案

但是这样的话在100%数据下会超时

再观察dp方程，发现是个卷积的形式

那么就可以用FFT优化dp方程了
总时间复杂度O(n^2log n+T)

由于输入数据很大，所以要使用读入优化