文理学院程序设计在线练习


蜜蜂的族谱

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 140   Accepted Submission(s): 96
Problem Description

蜜蜂是一个很特别的种群,他们修建具有很高美学价值的蜂窝,他们有清晰而且严格的“社会”结构,每只蜜蜂都努力的完成自己的角色,如果必要的时候他们愿意牺牲自己。

更让人惊奇的是蜜蜂的家族结构。雄性蜜蜂是由雌性蜜蜂无性繁殖而来,也就是说它是单亲的,只有母亲。而雌性蜜蜂就不一样了,它有双亲,有父亲与母亲。在家谱中,对一只雄性蜜蜂来说,它有一个母亲,一个”grandpa”和”grandma”,两个great-grandmas,一个great-grandpa,两个great-great-grandpas和三个great-great-grandmas,等等。

现在有一只好奇的雄性蜜蜂想知道在它的家谱中它的greatn-grandpas 和 greatn-grandmas有多少位。
说明: grandpa 和 grandma是这只雄性蜜蜂的母亲的父亲和母亲,分别用great0-grandpa 和 great0-grandma来表示。

如果蜜蜂A是这只雄性蜜蜂的greatn-grandpa(or grandma),那么A的父亲(如果有)和母亲是这只雄性蜜蜂的greatn+1-grandpa和greatn+1-grandma。

Input

第一行是一个整数T,表示测试实例的个数。接下来的T行中每一行包含一个整数n. ( 0 ≤ n ≤ 40)

Output

对每一个测试实例,输出两个整数,分别为这只雄性蜜蜂家谱中greatn-grandpas和greatn-grandmas的数量。

Sample Input
3
0
1
2
Sample Output
1 1
1 2
2 3
Source

2008年绍兴市大学生计算机技能竞赛