shunfurh
编程介的小学生
采纳率92.7%
2016-12-23 07:50 阅读 893
已采纳

Logs Stacking

Description

Daxinganling produces a lot of timber. Before loading onto trains, the timberjacks will place the logs to some place in the open air first. Looking from the sideway, the figure of a logs stack is as follows:

We have known that the number of logs in each layer is fewer than the lower layer for at least one log, and that in each layer the logs are connected in a line. In the figure above, there are 12 logs in the bottom layer of the stack. Now, given the number of logs in the bottom layer, the timberjacks want to know how many possible figures there may be.
Input

The first line of input contains the number of test cases T (1 <= T <= 1000000). Then T lines follow. Every line only contains a number n (1 <= n <= 2000000000) representing the number of logs in the bottom layer.
Output

For each test case in the input, you should output the corresponding number of possible figures. Because the number may be very large, just output the number mod 10^5.
Sample Input

4
1
2
3
5
Sample Output

1
2
5
34

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

2条回答 默认 最新

相关推荐