题目描述

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

• 捞山可乐 4 元/瓶。

• 百狮可乐 3 元/瓶。

• 非肠可乐 1 元/瓶。

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

输入格式

第一行：一个整数 $n$，表示顾客的人数。

接下来 $n$ 行：每行有两个整数 $x$ 和 $y$，分别表示顾客给的钱，和顾客想买的商品的编号。

y是1，表示买的是捞山可乐；

y是2，表示买的是百狮可乐；

y是3，表示买的是非肠可乐；

输出格式

输出共 $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$。