Problem 6014 --Fibonacci

6014: Fibonacci

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 54  Solved: 6
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][20kb]

Description

Dyian最近迷上了一个漂亮的女孩,并且这个女孩还是个酷爱Fibonacci数列的女孩!女孩说只有Dyian能够随口说出某个Fibonacci数的前k位(k<=4)她才会答应和他交往。(小于等于位数的便说出整个数)

现在Dyian决定向你求助了,请你帮帮他。

HINT

Fibonacci:F[0] = 0, F[1] = 1, F[i] = F[i-1] + F[i-2]。


Input

一个整数T表示数据组数

每组数据一行,包含两个数N(0<=N<=1000)K(1<=K<=4),表示第几个Fibonacci数(即F[N])的前K位。


Output

每组数据一行,一个数,表示该Fibonacci数的前K位。


Sample Input

4
0 1
1 2
5 3
35 4

Sample Output

0
1
5
9227

HINT

Source

[Submit][Status]