ASCDFIB - Ascending Fibonacci Numbers


John is trying to learn the Fibonacci sequence. This is what he has learned so far. The first two terms of the sequence are f(1) = 0 and f(2) = 1.  The next term f(n) is then calculated by adding the previous two terms f(n-1) and f(n-2). Therefore,

f(1) = 0

f(2) = 1

f(3) = f(2) + f(1) = 1 + 0 = 1

f(4) = f(3) + f(2) = 1 + 1 = 2

f(5) = f(4) + f(3) = 2 + 1 = 3

f(6) = f(5) + f(4) = 3 + 2 = 5

After calculating this for a while, John realized that the values are becoming too big. In order to keep the values small, John changed his algorithm. Instead of calculating f(n) = f(n-1)+f(n-2), he decided he will calculate f(n) = ( f(n-1)+f(n-2) ) % 10^5.

Now John wants to do some research on his new modified Fibonacci sequence. He will give you an integer A (A<=10^5) and an integer B (B<=10^6). You have to output all the terms from f(A) to f(A+B) in ascending order (non-decreasing order). But printing so many numbers is too much of a hassle. So, if there are more than 100 terms in the output, then only print the first 100.

Input

The first line contains an integer T (T<=100), which is the number of test cases.
Each test case contains two positive integers A and B as mentioned before.

Output

For each test case, print case number (Check sample output) and then print the terms from f(A)  to f(A+B) in ascending order (non-decreasing order). If there are more than 100 terms in the output, then only print the first 100.

Example

Input:
3
1 3
3 3
100 1

Output:
Case 1: 0 1 1 2
Case 2: 1 2 3 5
Case 3: 15075 69026

hide comments
eightnoteight: 2015-09-05 08:08:13

enjoyed solving it in python

Glenda Emanuella Sutanto: 2015-06-19 06:25:06

finally AC after 2 WAs and 1 TLE!!! :))) i just changed it into counting sort and it got AC xD

Glenda Emanuella Sutanto: 2015-06-18 06:35:16

@samiul / the problem setter : my submission 14478814 please check it, thankyou so much

Glenda Emanuella Sutanto: 2015-06-18 06:31:08

for sorting i just used C++ STL but i got WA not TLE, so if i change it into counting sort will it get AC?

If A..(A+B) > 100, i've already printed for the first 100 and no trailing spaces. What should i do ? :( help me please

Glenda Emanuella Sutanto: 2015-06-18 06:26:56

why wa :(

fibonacciprw: 2015-06-13 06:53:53

If you're getting WA: check that you're never printing more than 100 numbers, and check that you're not printing any trailing spaces. Those two things caused me to get five WA. :'(

newbie: 2015-06-09 08:42:02

Finally accepted !!!

NEXES: 2015-06-06 08:19:20

conting sort!!!!!!...........AC

Gannu_raj: 2015-06-06 07:12:12

Finally with heap AC!!! :)

Last edit: 2015-06-06 08:50:05
BRAIN: 2015-06-05 15:43:44

Finally AC! Using counting sort


Added by:forthright48
Date:2013-09-13
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Editorial