Chico told his students that from now on, they would be referenced by numerical codes of up to 12 digits in official communications (emails and tasks). Then, he gave each student a card with a unique number written on it. The students quickly assumed this number was their code — but to their surprise (and Levi’s despair), Professor Chico explained that this was not their actual code.

A student’s code is the term at the position (indexed from 1) in a special ordered sequence S, where that position is the number written on their card. The sequence S has a unique property: each number in it, when decomposed into prime factors, can only include primes from a set of N numbers written on the board by the teacher. To make Levi’s life even harder, the set of primes changes every week, so he always has to recalculate his code to avoid missing deadlines.

Your task is to help Levi. Given the set of prime numbers written on the board during the week and the number on Levi’s card, determine what his weekly cod

Input

The input consists of multiple test cases.

Each test case begins with a line containing two integers N (1 ≤ N ≤ 10²) and M (1 ≤ M ≤ 10⁵) representing respectively the number of prime numbers written on the board by Professor Chico and the number on the student's card.

The second line contains N distinct prime numbers P₁, P₂, ..., Pₙ (2 ≤ P_i < 10⁶), which form the allowed prime factor set for the week.

Input ends when a line with N = 0 and M = 0 is encountered.

Output

The output consists of a single line for each test case, containing Levi's weekly code.

Example

Input:
2 1
2 3
2 10
2 3
3 10
2 3 5
3 10
3 7 13
0 0

Output:
2
24
15
81