Ureckon is underway and there are a huge number of coordinators.  There are $10^9$ number of tasks to be done numbered $1 \text{ to } 10^9$. However, they need to be assigned to the many coordinators.There are 3 coordinators who are hardworking and they have the maximum amount of responsibility. The three coordinators are : - Soumyadip, Tathagatha & Sangram. Soumyadip can only be assigned the tasks which are quirky numbers. Quirky numbers are positive integers which can be divided by the ID a or b or c. The ID a or b or c are the ID of the three coordinators respectively.The event convenor wants to know the $n^{th}$ task assigned to any of the three coordinators. Help him find the task number assigned.

Input Format:

The 1st line contains $T$, the number of testcases. $T$  lines continue.
Each line of the testcase contains four integers $n,a,b,c$.

Output Format:

Print the $n^{th}$ task number.

Constraints:

$1 \leq T \leq 10^5$
$1 \leq n,a,b,c \leq 10^9$
$1 \leq a*b*c \leq 10^{18}$
It's guaranteed that the result will be in range $[1,2*10^9]$