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