2011年7月16日 星期六

974 - Kaprekar Numbers


有一種稱為Kaprekar numbers的數,該數的平方可以分解成兩個整數,這兩個整數的和等於原數值。例如55的平方為55^2=3025,拆開分解成30與25兩數使得30+25=55。另外還有一個規則:分解出來的兩個整數必需大於零,所以10並非一個Kaprekar number,因為若10^2=100且10+0=10,但是由於第二個整數為0,所以10並非Kaprekar number。

The Problem

給定一對整數,請你找出介於這兩個整數之間所有的Kaprekar numbers。

Input

輸入的第一列有一個整數N(1 <= N <= 1000),表示有幾組測試資料。接下來有N列,每列有兩個以空白字元隔開的整數INF與SUP(2 <= INF <= SUP <= 40000),請出找出介於區間[INF, SUP]內的所有Kaprekar numbers。

Output

請在每組輸出資料的第一列輸出case #NUM(NUM表示測試資料的編號)。
接下來請你由小到大依序列出介於該組區間內的所有Kaprekar numbers,每個數獨立一列。若找不到Kaprekar number請輸出"no kaprekar numbers"
每組測試資料之間請輸出一列空行。

Example Input

3
2 90
30 35
50 55

Example Output

case #1
9
45
55

case #2
no kaprekar numbers

case #3
55

沒有留言:

張貼留言