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\)