불사 돌고래

불사 돌고래는 직선의 저편에 살면서 살아 있는 갈매기를 잡아먹는다. 갈매기를 그쪽으로 실어 나르는 일은 연방법이 금지하고 있지만, 그건 또 다른 이야기다.

과학자 Leo O. Pisa는 불사 돌고래를 오래 관찰해 몇 가지 사실을 알아냈다. 돌고래 한 쌍은 해마다 새끼 두 마리, 곧 한 쌍을 낳는다. 새끼가 다 자라 스스로 새끼를 낳기까지는 꼬박 한 해가 걸린다. 그래서 갓 태어난 한 쌍에서 시작하면 1년째 말에는 여전히 한 쌍이 있고, 이 쌍은 이제 다 자란 상태다. 2년째 말에는 새로 태어난 한 쌍이 생기고 다 자란 한 쌍도 그대로 남는다.

해마다 작년에 살아 있던 돌고래는 하나도 빠짐없이 그대로 살아 있고, 두 해 전에 이미 살아 있던 쌍은 저마다 새끼 한 쌍을 낳는다. 다만 세상이 불사 돌고래로 뒤덮이지 않도록, 쌍의 수가 10억($10^9$) 쌍 이상이 되면 그중 10억 쌍이 홀연히 사라진다. 그래서 어떤 해에는 개체 수가 완전히 0이 되기도 하고, 그런 해의 이듬해에는 한 쌍이 다시 나타난다. 결국 Y년째 말에 살아 있는 쌍의 수는 $fib(Y) \bmod 10^9$이며, 여기서 $fib$는 $fib(1) = fib(2) = 1$인 피보나치 수열이다.

연도별 쌍의 수를 적으면 다음과 같다.

1년째가 시작될 때 갓 태어난 한 쌍이 있다고 하자. Y년째 말에 살아 있는 불사 돌고래 쌍의 수를 구하는 프로그램을 작성한다. 불사 돌고래는 우주가 정확히 $2^{48} = 281{,}474{,}976{,}710{,}656$년 동안만 존재한다고 믿으므로, 그보다 뒤의 해는 다루지 않아도 된다.

첫 줄에 데이터 집합의 개수 $P$가 주어진다 ($1 \le P \le 1000$). 각 데이터 집합은 서로 독립이며 모두 같은 방식으로 처리한다.

이어지는 $P$개의 줄에는 각각 공백으로 구분된 두 정수 $K$와 $Y$가 주어진다. $K$는 데이터 집합 번호로 1부터 $P$까지 순서대로 매겨진다. $Y$는 돌고래가 살아온 햇수이며 $1 \le Y \le 2^{48}$이다.

각 데이터 집합마다 한 줄씩 출력한다. 한 줄에는 데이터 집합 번호 $K$, 공백 하나, $Y$년째 말에 살아 있는 불사 돌고래 쌍의 수를 차례로 쓴다.