Un entero positivo es mágico si es divisible por \(a\) o por \(b\). Encuentra el \(n\)-ésimo número mágico.

Entrada

La primera línea tiene \(T\) \((1 \le T \le 1000)\). Cada una de las siguientes \(T\) líneas tiene \(n\) \((1 \le n \le 10^9)\), \(a\) y \(b\) \((2 \le a, b \le 4 \cdot 10^4)\).

Salida

Para cada caso, una línea con el \(n\)-ésimo número mágico módulo \(10^9 + 7\).

Ejemplo 1

Entrada

3
1 2 3
4 2 3
5 2 4

Salida

2
6
10