一只小蜜蜂… Time Limit: 2000/1000 MS (java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 69330 Accepted Submission(s): 24966

PRoblem Description

有一只經(jīng)過訓(xùn)練的蜜蜂只能爬向右側(cè)相鄰的蜂房，不能反向爬行。請(qǐng)編程計(jì)算蜜蜂從蜂房a爬到蜂房b的可能路線數(shù)。 其中，蜂房的結(jié)構(gòu)如下所示。

Input

輸入數(shù)據(jù)的第一行是一個(gè)整數(shù)N,表示測(cè)試實(shí)例的個(gè)數(shù)，然后是N 行數(shù)據(jù)，每行包含兩個(gè)整數(shù)a和b(0 < a < b< 50)。

Output

對(duì)于每個(gè)測(cè)試實(shí)例，請(qǐng)輸出蜜蜂從蜂房a爬到蜂房b的可能路線數(shù)，每個(gè)實(shí)例的輸出占一行。

Sample Input

2 1 2 3 6

Sample Output

1 3

Author

lcy

由圖可以輕易看出遞推關(guān)系： 從start->end 直接到end有兩點(diǎn)end-1和end-2 相當(dāng)于到end的路徑等于到end-1的路徑加上到end-2的路徑 end-1又可以拆分為end-2和end-3 。。。。 。。。。 得到公式f(n)=f(n-1)+f(n-2)

若從start->end 相當(dāng)于從1->end-start+1