Background

Description

夏荷在⻛国的市场中买东⻄。
⻛国交易⽤的是⻛⽯（她们那⾥的钱），按照其品质，可分为13种，其价值分别为：1,2,5,10,20,50,100,200,500,1000,2000,5000,10000
现在，夏荷⼿上有⼀块价值为A的⻛⽯，她急需筹集价值和刚好为B的⼀些⻛⽯（B < A）。她的想法是，每次买⼀些东⻄（每个东⻄的价值也是上⾯那13种之⼀），然后让店家找零，如果店家找完零钱后⾃⼰还是不能凑出，则她会继续买⼀些东⻄（⽤⼿上的某个⻛⽯），让店家继续找零，直到她拥有的钱（指找回的钱和⼿头本来就有的钱）可以凑出为⽌（如果夏荷⼀直只买价值为1的东⻄，我们知道她⼀定会在某个时刻凑⻬，故她⼀定可以达到⽬的），现在，夏荷想知道，她最少需要买多少价值的东⻄，才能保证她能够凑出（我们假设店家每次找零只保证总价值是正确的，我们在买东⻄之前不知道他的找零⽅案，⽐如现在需要找9，店家可能给你2,2,5，也可能给你1,1,2,5）。

Format

Input

第⼀⾏包含⼀个整数：T，表⽰测试组数。
接下来⾏，每⾏两个数A B。

Output

对于每组数据，输出包含⼀个整数：C，表⽰最少花的钱数。

Sample

Input

2
10 2
5 1

Output

1
2

Explanation

第⼀组数据，夏荷只需要先买⼀个价值为1的东⻄，店家需要找价值和为9的⼀些⻛⽯，⽽所有⽅案中，要么直接有2，要么有⾄少两个1，所以必定可以凑出2，故夏荷只需要买⼀个价值为1的东⻄就⾏了。
第⼆组数据，假如夏荷买了⼀个价值为1的东⻄，店家需要找总价值为4的⼀些⻛⽯，那么店家可以找两个2，这样夏荷⽆法凑出1，故夏荷⾄少要买价值和为2的东⻄，假如夏荷买了⼀个价值为2的东⻄，那么店家需要找总价值为3的⻛⽯，因为3是奇数，所以店家的找零离⼀定有1，故2就⾏了。

Limitation

对于30%的数据，1 ≤ B < A ≤ 10;
对于50%的数据，1 ≤ B < A ≤ 100;
对于100%的数据，1 ≤ B < A ≤ 10000，1 ≤ T ≤ 72，保证⼀定是上⾯13个数之⼀.
1s, 256000KiB for each test case.

Hint

Source

CDQZ TEST