ABC University has k departments. Each department is assigned a department number. There are many students in each department. The university assigns roll numbers to each student such that the number is divisible by the department number. For example if department number is 5, the students can only get roll numbers 5, 10, 15, etc. The purpose is to identify the department of a student easily from his roll number. So if a number is divisible by more than one department number, then that number will not be assigned to any student (so that there will not be any ambiguity). For example if we have departments 5 and 7, then 35, 70, 105, etc are not used because they are divisible by both numbers. Everything was going fine until one day, someone hacked into the University database and erased the roll number column in the students table! The Database administrator knows that,
‧ All valid roll numbers (the valid roll numbers are numbers divisible by one and only one department number) less than 1015 were there in the Database.
‧ All the records were sorted by roll number before the hacker erased them, and the hacking did not change the order of records
Now given the position (1 based index) of the record in the database, can you find out the roll number corresponding to that record quickly?
The first line contains one integer t, the number of testcases (1 <= t <= 50).
This will be followed by 't' test cases, each containing 2 lines.
The first line of each test case gives two numbers k and n separated by space.
The second line contains k space separated integers specifying the department numbers of each department.
For each test case print the roll number corresponding to the nth record in the database. Output of each test-case should be on a separate line.
2 2 4 2 3 3 10 6 11 20
8 36
Migrated from old NTUJ.
ACM-ICPC Asia-Amritapuri Site 2009
| No. | Testdata Range | Score |
|---|