You are given two integers $A$ and $B$. Print the sum of numbers that cannot be formed using any combination of $A$ and $B$ . If the sum is infinite print $-1$. Since the answer can be large, print the sum modulo $10^9+9$.

A combination of $A$ and $B$ can be represented as an integer C that is denoted as $x*A+y*B$ where $x$ and $y$ are whole numbers.

INPUT FORMAT:

The first line contains an integer $T$, denoting the number of test cases. Each of the next $T$ lines contains two space separated integers $A$ and $B$.

OUTPUT FORMAT:

For each test case print the answer in a new line.

CONSTRAINTS:

$1\leq T\leq10^5$

$1\leq A,B\leq10^9$

$B=A+1$