老电影
说明
1930年上映了一部非常著名的电影《三十九级台阶》，小磊最近观赏了这部历史悠久的电影，小磊觉得非常好看，就介绍给了小丽： 歌剧院里,杂耍表演结束的舞台上,报幕员走上舞台,隆重介绍记忆先生梅里克.借惊人的记忆,梅里克回答着观众各种刁钻古怪的问题.嘈杂的人群中,加拿大男人汉纳提问了一个有关加拿大地理方面的问题,记忆先生准确地给出答案.枪声!两声枪响,让原本嘈杂不堪的歌剧院顿时陷入混乱.人群涌向出口,一个陌生而漂亮的女子紧跟着汉纳,在拥挤的人群中挤出歌剧院,随汉纳来到他租住的布兰特公寓. 女子自称施密斯,受雇于英国间谍机构,因保护英国空军防空机密而遭到陌生人的追踪.施密斯的任务是前往苏格兰,与一个右手小拇指缺一截的男人接头.男人是秘密间谍组织三十九级台阶的负责人.透过窗帘,汉纳确实看到窗外的墙根下站着两个神秘的男子.入夜,施密斯突然闯进汉纳的房间,丢下一句快走!下一个将是你后,倒地死去,背后插着一把尖刀. 怀着恐惧而疑惑的心情,汉纳逃出旅馆,搭上火车,前往苏格兰.火车上,汉纳从报纸上看到警察已经发现了施密斯的尸体,自己却成了凶杀犯正被警方通缉.陌生女人的告密,让警察闻讯而至.汉纳机智的甩开警察的追捕,跳下火车,来到苏格兰的一处农庄. 警察尾随而来.贪财的农夫将汉纳出卖给警察,好心的农妇却给了汉纳一条生路.翻山,越岭,涉水,斩棘,汉纳依然遭到警察的追捕.此时,汉纳按照施密斯临死前留下一张地图,找到乔纳教授的山庄.适逢酒神节.乔纳巧妙地支走警察,露出庐山真面.汉纳发现,乔纳竟然就是施密斯说的那个小拇指缺一截的接头人,而施密斯的真名叫安娜·贝拉. 接下来发生的事情更加扑朔迷离,汉纳的处境也越来越危险.当汉纳从扑朔迷离中发现空军机密与三十九级台阶秘密间谍组织有关时,已经是在回到伦敦后的歌剧院.记忆先生的回答,提醒了汉纳.原来,间谍组织是想利用记忆先生惊人的记忆,将空军机密带出英国.真相在最后一刻揭露,清白在最后一刻洗清,乔纳教授在最后一刻现形,记忆先生却在最后一刻用生命保护了国防机密.介绍完后，小丽忽然说了一句,三十九阶台阶，你有多少种方法上去，小磊深知，自己腿短，自己一下子最多能上两节，小磊先算上一阶台阶有一种方法能上去，上两阶有两种。。。。小磊算了一个晚上也没有算到第39阶，于是就去问被人称作学霸的ACM的同学，为了不失面子，当小磊问你上 n 阶台阶有多少种方法时，你能快速告诉他么？
输入格式
第一行是一个整数 t ，表示有 t 组测试数据；每组测试数据只有一个整数 n，表示有 n 阶台阶（0 < n < 40）;
输出格式
对于每组测试数据 n ，输出一个整数，表示有多少种方法可以上去；2
1
21
2