Under construction

Still being built. Things may change

Taekwondo King

Interview

Time limit2sMemory limit128 MB

Summary
With S < T, using combo A doubles S but adds 3 to T, and combo B adds 1 to S. Find the fewest kicks that make S equal T.
Level

Medium6 of 10

Topics
Dynamic programming, Greedy, Math, Brute force
Solved
No attempts yet

Problem

Taegyun is in the middle of a taekwondo bout. He is behind on points, so from now on he fights seriously and tries to catch up fast.

Taegyun has two combo kicks.

  1. Combo A is a huge combo that gains as many points as his current score. One use turns Taegyun's score SS into 2S2S. The risk is that the opponent also scores 3 points, so TT becomes T+3T + 3.
  2. Combo B gains 1 point. One use turns SS into S+1S + 1.

He may use the two combos any number of times in any order, and the scores are compared after each single kick. Given Taegyun's current score SS and the opponent's current score TT, write a program that finds the minimum number of combo kicks that makes SS and TT equal.

Input

The first line contains the number of test cases CC (1≤C≤1001 \le C \le 100). Each of the next CC lines contains the current scores SS and TT for one test case, separated by a space. (1≤S<T≤1001 \le S < T \le 100)

Output

For each test case, print the minimum number of combo kicks that makes SS and TT equal, one per line.

Examples1

  1. Example 1

    Input
    6
    10 20
    2 7
    15 62
    10 37
    11 50
    34 59
    
    Expected output
    3
    3
    4
    4
    5
    25