## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Divisible by 3 CodeChef Solution | CodeChef Problem Solution 2022

Stack likes the number $3$ a lot.

He has two non-negative integers $A$ and $B$.
In one operation, Stack can do either of the following:

• $A:=|A-B|$ (change $A$ to $|A-B|$)
• $B:=|A-B|$ (change $B$ to $|A-B|$)

Note that $|X|$ denotes absolute value of $X$. For example $|-7|=7$ and $|4|=4$.

Find the minimum number of operations after which at least one integer out of $A$

and $B$ becomes divisible by $3$.

### Input Format

• The first line of input contains a single integer $T$, denoting the number of test cases. The description of $T$ test cases follows.
• The only line of each test case contains two integers $A$ and $B$.

### Output Format

For each test case, output in a single line the minimum number of operations after which at least one integer out of $A$ and $B$ becomes divisible by $3$.

### Constraints

• $1\le T\le {10}^{5}$