HZNUOJ

【C系列4.8】函数训练之被甩

Tags:   f
Time Limit:  5 s      Memory Limit:   32 MB
Submission:4767     AC:1981     Score:11.68

Description

cyn小朋友今天看了一个小故事,讲的是zp同学在大学中被各种女生甩的惨痛经历,故事上说zp在大学第一天就和一个女神级别的大一新生表白了,然后被华丽丽的拒绝了,第二天又表白了m个女生,再次被华丽丽的拒绝了m次,从那一天开始,他坚持不懈地和各种女生表白,每天表白的次数是前一天的次数加上再前一天的次数的两倍,终于在30天后被一位女生接受了,请问他在第30天被拒绝了几次?

Input

第一行有一个整数T,代表有几组测试样例。
接下来的T行每行有一个整数m(1 <= m <= 100000),代表第二天的被拒绝的次数

Output

对于每一个测试样例输出他被拒绝的次数p。

Samples

input
3 1 2 3
output
357913941 536870912 715827883

Hint

 输入,输出,请用%lld

Author

MA, Wuyuan