Krishna and Coffee Shop

All submissions for this problem are available.
Krishna loves visiting coffee shop in search of finding a _date_ for himself. It's been years now since he started visiting the coffee shop, but no luck till now. But that doesn't mean he'll stop trying. He visits the coffee shop on a regular basis, at every $K$ units of time. This means that his visits in the coffee shop happen at time $K, 2K, 3K, \dots$ respectively. The main problem is that he doesn't know anything about the girls visiting the coffee shop, maybe that's why he's been so lonely all these years. A total of $N$ girls visit the coffee shop on a regular basis, and for each valid $i$, the $i^{th}$ girl visits the coffee shop at every $A_{i}$ units of time. Out of the $N$ girls, only one girl needs to be selected. Now, pitying upon his situation, you've decided to tell him the minimum amount of time that he'll have to wait to meet a girl in the coffee shop, just to keep his hope alive. Waiting time is the total time elapsed. For example, if there is a girl who visits the coffee shop every $3$ units of time, and Krishna visits at every $2$ units of time, then Krishna can meet the girl at his $12^{th}$ visit (it would be the girl's $8^{th}$ visit). In this case the wait time is $24$ units. You need to find a suitable girl and minimize the wait time. Can you do that for him? **Note:** Assume that time is discrete, and if Krishna is in the coffee shop at time $K$ (his first visit), then he's not there at time $K + 1$ (when $K \neq 1$). This is also true for each of the $N$ girls. Also, everyone starts at the same time, assume it to be $0$. ### Input:  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two space separated integers $N$ and $K$.  The second line contains $N$ space separated integers $A_{1}, A_{2}, \dots, A_{N}$. ### Output: For each test case print a single line containing an integer denoting the minimum amount of time Krishna has to wait. If this value exceeds $10^{18}$, print $1$ instead, because that's the expected value of one's lifetime, and he can't wait for his whole life. ### Constraints:  $1 \leq T \leq 10^{5}$  $1 \leq N \leq 10^{5}$  $1 \leq K \leq 10^{18}$  $1 \leq A_{i} \leq 10^{18}$, for each valid $i$  Sum of $N$ over all test cases doesn't exceed $10^{6}$ ### Subtasks:  **10 points:** $1 \leq N \leq 10$ $1 \leq K \leq 100$ $1 \leq A_{i} \leq 100$, for each valid $i$ Sum of $N$ over all test cases doesn't exceed $100$  **30 points:** $1 \leq N \leq 10^{3}$ $1 \leq K \leq 10^{9}$ $1 \leq A_{i} \leq 10^{9}$, for each valid $i$ Sum of $N$ over all test cases doesn't exceed $10^{4}$  **60 points:** original constraints ### Sample Input: 2 3 3 1 2 4 5 4 17 12 46 8 31 ### Sample Output: 3 8 ### Explanation:  **Example Case 1:** He can meet the first girl at his first visit (it would be the girl's $3^{rd}$ visit). So, $3$ is the minimum wait time.  **Example Case 2:** He can meet the fourth girl at his second visit (it would be the girl's $1^{st}$ visit). So, $8$ is the minimum wait time.Author:  ankushkhanna 
Editorial  https://discuss.codechef.com/problems/DWW19B 
Tags  ankushkhanna, ankushkhanna, dwwu2019, easy, gcd, lcm, math, observations 
Date Added:  28122019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 