题目描述

小博很喜欢喝可乐，他对可乐颇有研究，他昨晚做了一个梦，梦见了自己开了一家可乐商店，有很多人过来购买可乐，而且你现在是他的助手。 可乐商店中的商品有：

1. 捞山可乐 4 元/瓶。
2. 百狮可乐 3 元/瓶。
3. 非肠可乐 1 元/瓶。
   他只准备了 10 元、5 元、1 元三种纸币用于找零。假设每种都有无数张，每名顾客 一次只买一瓶可乐，你作为他的助手，该如何找零，才能使得找出的零钱张数最少。

输入格式

输入文件 shop.in。 第一行，一个整数 n，表示顾客的人数。 接下来 n 行，每行有两个整数 x 和 y，x 表示顾客给的钱，y 表示顾客想买的商品的 编号。

输出格式

输出文件 shop.out。 输出 共 n 行，每个表示每组数据要找出零钱的最少张数。

1
20 2

4

样例 1 解释

顾客支付了 20 元，购买 2 号商品百狮可乐，实际需付 3 元，需找零 17 元，最少张数 为 4 张，分别是 1 张 10 元，1 张 5 元，2 张 1 元。

3
20 1
50 3
100 2

3
9
12

数据范围

50%的数据，保证 $1≤n≤100，4≤x≤1000$。
100%的数据，保证 $1≤n≤100000，4≤x≤10^{12}，1≤y≤3$。