出题人曾经出过一个这样的题。他是在一本他的数学国家集训队的同学的手里借来的影印版 《俄罗斯组合分析问题集》那里得到的灵感。但是出题人本身没有这个实力，于是他请他的同学帮他出完了这一道题。
设函数为：
如果出题人是强者，他会让你求：
但显然出题人没有这样的实力。
所以他让你求：
本题含有多组数据。
第一行为一个整数 ，表示数据组数。
对于每组数据，一行一个整数，表示 。
对于每组数据，一行一个整数，表示答案。
1 1
5
请注意，
对于全部数据，满足：
