Immortal Porpoises

Immortal porpoises live on the other side of straight lines and eat live seagulls, although federal law forbids carrying gulls over to them. That is another story.

The scientist Leo O. Pisa studied immortal porpoises for years and worked out how they breed. A single pair produces two babies, that is one new pair, every year, and a newborn pair needs a full year to mature before it can produce a pair of its own. So if you start with one newborn pair, at the end of year 1 you still have that one pair, now mature. At the end of year 2 you have a newborn pair as well as the mature pair.

Every year all the porpoises that were alive last year are still alive, and every pair that was already alive two years earlier produces one new pair. To keep the world from filling up with immortal porpoises, whenever the count reaches one billion ($10^9$) pairs or more, one billion pairs quietly vanish. Some years the population drops to zero, and in the year after that a single pair appears again. The number of pairs alive at the end of year Y is therefore $fib(Y) \bmod 10^9$, where $fib$ is the Fibonacci sequence with $fib(1) = fib(2) = 1$.

The year by year pair counts start like this.

Assume you start with a newborn pair at the beginning of year 1. Write a program that reports how many immortal porpoise pairs are alive at the end of year Y. Immortal porpoises believe the universe lasts exactly $2^{48} = 281{,}474{,}976{,}710{,}656$ years, so you never have to deal with a later year.

The first line contains the number of data sets $P$ ($1 \le P \le 1000$). The data sets are independent and are all processed the same way.

Each of the next $P$ lines contains two space separated integers $K$ and $Y$. $K$ is the data set number, numbered 1 to $P$ in order. $Y$ is the number of years the porpoises have been alive, with $1 \le Y \le 2^{48}$.

Print one line for each data set. The line holds the data set number $K$, a single space, and the number of immortal porpoise pairs alive at the end of year $Y$.