题目描述

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

输入输出格式

输入

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

输出

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

样例

输入1

3
10 2
5 3
85 2

输出1

3
4
10

时间及空间限制

1s, 256MB.