TopCoder

Thumb pixelcat
PixelCat
喵喵 >//////<

User's AC Ratio

88.9% (8/9)

Submission's AC Ratio

22.0% (13/59)

Tags

Description

大家都知道養兔子是一件非常麻煩的事情。

簡單的說,每一對小兔子在一天後會長成大兔子、每一對大兔子每天都會生出一對小兔子。

第一天你家中買了一對大兔子(hh)。
總共有一對兔子。

第二天那對大兔子生出了一對小兔子。
總共有兩對兔子。

第三天那對大兔子生出了一對小兔子、那對大兔子生的小兔子長成了大兔子。
總共有三對兔子。

第四天那對大兔子生出了一對小兔子、那對大兔子生的小兔子長成的大兔子生出了一對小兔子。那對大兔子第三天生的小兔子長成了大兔子。
總共有五對兔子。

第五天那對大兔子生出了一對小兔子、那對大兔子生的小兔子長成的大兔子生出了一對小兔子。那對大兔子第三天生的小兔子長成的大兔子生出了一對小兔子。
那對大兔子第四天生的小兔子長成了大兔子。那對大兔子生的小兔子長成的大兔子生的小兔子長成了大兔子。
總共有八對兔子。

而當然,兔子飼料的消耗量是非常大的。有一天你和鴨王去採買兔子飼料時發現正在進行買一送一特賣。

你已經養兔子養了A天、鴨王養了B天。你們打算兩人各買K份飼料讓兩人能把飼料平分給各自家中的每"隻"兔子並且沒有剩餘,當然飼料是不能切割的。

(K必須是一個正整數。)

你希望花儘量少的錢,請寫個程式來計算你至少要買多少份飼料。因為這個數字可能很大,輸出這個數字除以10,007的餘數。

對了,一對代表兩隻喔。

Input Format

輸入第一行有一個正整數T(T <= 1,000),表示接下來有多少詢問。
接下來每行有兩個正整數A B,表示你跟鴨王各養兔子養了幾天。

保證1 <= A, B <= 1,000,000

Output Format

對每筆詢問輸出一個[0,10007)內的整數,表示K除以10,007的餘數。

Sample Input

2
1 2
2 3

Sample Output

4
12

Hints

對於第二個詢問,你養了兩天共有2對兔子、鴨王養了三天共有3對兔子。

所以你至少需要12份飼料。你每"隻"兔子分得3份、鴨王每"隻"兔子分得2份飼料。

Problem Source

原TIOJ1722 / Problem Setter : ATP
Source : 經典問題

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1