（原案：horitaka, 改題：toam）

\(M=30\) とします．多重集合ではなくて， \(2\) 冪からなる単調増加列を考えることにします．

\(O(M^3)\) / testcase 解法

（補題） \(|A|\geq 2\) であるような単調増加列について， \(A\) の総和を \(n\) とし， \(e\) を \(2^e\lt n\) をを満たす最大の整数とする．このとき， \(A\) の prefix であって総和が \(n-2^e\) になるものが存在する．

（証明）存在しないと仮定すると，仮定から \(\displaystyle \sum_{i\lt k}A_i\lt n-2^e\lt \sum_{i\lt k+1}A_i\) を満たす \(k\) が存在する．このとき \(\displaystyle \sum_{i\geq k}A_i\) は \(A_k\) の倍数である必要があるが \(\displaystyle 2^e-A_k\lt \sum_{i\geq k}A_i\lt 2^e\) となり矛盾．

整数 \(n,L,R(L\leq R)\) に対し，次を満たす単調増加列 \(A\) すべてに対する \(\prod A\) の総和を \(g(n,L,R)\) とします．

• \(\sum A=n\)
• \(A\) の要素は \(2^L,2^{L+1},\ldots,2^R\)
• \(2^L,2^R\in A\)

補題から以下が成り立ちます．

• \(2^L=2^R=n\) のとき \(g(n,L,R)=2^R\)
• そうでないとき \(e\) を \(2^e\lt n\) を満たす最大の整数として \(g(n,L,R)=\displaystyle \sum_{L\leq m_1\leq m_2\leq R} g(n-2^e,L,m_1)\times g(2^e,m_2,R)\)

これを繰り返し適用することで以下が成り立ちます．

• \(n=2^{e_1}+2^{e_2}+\ldots+2^{e_K}\ (e_1\lt e_2\lt \ldots \lt e_K)\) として \(g(n,L,R)=\displaystyle\sum_{L= l_1\leq r_1\leq l_2\leq r_2\leq \ldots \leq l_K\leq r_K=R} \prod g(2^{e_i},l_i,r_i)\)

よって \(f(n)=\displaystyle\sum_{0\leq L\leq R\lt M}g(n,L,R)=\sum_{0\leq l_1\leq r_1\leq l_2\leq r_2\leq \ldots \leq l_K\leq r_K\lt M} \prod g(2^{e_i},l_i,r_i)\) です．

\(g(2^i,L,R)\) をあらかじめ前計算で求めておけば，この式をもとに \(f(n)\) を dp で \(O(M^3)\) などで求めることができます．

\(O(M)\) / testcase 解法

\(n=bottom+2^{15}top(0\leq bottom,top\lt 2^{15})\) とすると同様の議論により \(g(n,L,R)=\displaystyle \sum_{L\leq m_1\leq m_2\leq R} g(bottom,L,m_1)\times g(2^{15}top,m_2,R)\) が成り立ち，したがって \(f(n)=\displaystyle \sum_{0\leq l_1\leq r_1\leq l_2\leq r_2\lt M} g(bottom,l_1,r_1)\times g(2^{15}top,l_2,r_2)\) です． \(g(bottom,L,R)\) や \(g(2^{15}top,L,R)\) をあらかじめ前計算で求めておけば，この式をもとに \(f(n)\) を dp で \(O(M)\) などで求めることができます．前計算は計算量 \(O(2^{M/2}M^2)\) ででき，全体の計算量は \(O(2^{M/2}M^2+TM)\) です．テストケースごとの計算は軽いので，これで間に合います．

実装例