Problem 21253 --A:自动贩卖机

21253: A:自动贩卖机

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

Description

宿舍楼下有自动贩卖机后,教学楼下也有了。某台自动贩卖机只有以下3种饮料可以买:
1.脉动,4元。
2.旺仔牛奶,3元。
3.矿泉水,1元。
并且这台自动贩卖机很高级,只会找10元,5元,1元这3种纸币,不会找硬币,而且有无数张。那么在顾客一定能购买成功的情况下,它要怎样找零钱,才会使自己找出的纸币张数最少呢。

Input

输入数据的第一行是一个整数T,表示有T组测试样例,接着是T行数据,每行两个整数n和m,n表示顾客投入贩卖机的金额,m表示顾客要买饮料的序号。T<100,0<n<=100,0<m<=3。

Output

对于每组测试样例,输出该自动贩卖机要找出零钱的最少张数,并独占一行。

Sample Input

3
10 2
5 3
85 2

Sample Output

3
4
10

HINT

Source

[Submit][Status]