Un número positivo es feo si es divisible por \(a\), por \(b\) o por \(c\). Encuentra el \(n\)-ésimo número feo.

Entrada

La primera línea tiene \(T\) \((1 \le T \le 1000)\). Cada una de las siguientes \(T\) líneas tiene \(n\), \(a\), \(b\) y \(c\) \((1 \le n, a, b, c \le 10^9)\). Se garantiza que la respuesta es a lo más \(2 \cdot 10^9\).

Salida

Para cada caso, una línea con el \(n\)-ésimo número feo.

Ejemplo 1

Entrada

4
3 2 3 5
4 2 3 4
5 2 11 13
1000000000 2 217983653 336916467

Salida

4
6
10
1999999984