10645: Fibonacci

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:2 Solved:0

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 Copy

4
0 1
1 2
5 3
35 4

Sample Output Copy

0
1
5
9227