问题 6014 --Fibonacci

6014: Fibonacci

时间限制: 1 Sec  内存限制: 128 MB
提交: 54  解决: 6
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][20kb]

题目描述

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

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

HINT

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


输入

一个整数T表示数据组数

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


输出

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


样例输入

4
0 1
1 2
5 3
35 4

样例输出

0
1
5
9227

提示

来源

[提交][状态]