크랩의 대포

크랩 씨는 유명한 엔지니어다. 그는 최근 팔린드롬 캐논이라는 새롭고 매우 강력한 무기를 발명했다. 이 대포를 발사하려면 제한이 없는 알파벳으로 이루어진 길이 $\ell$의 문자열을 장전해야 한다.

문자열의 회문 접두사 집합(PPS)은 길이가 $i$인 접두사가 회문이 되는 모든 수 $i$ ($1 \le i \le \ell$)의 집합이다. 예를 들어 "abacaba"의 PPS는 $\{1, 3, 7\}$이고, "aaaa"의 PPS는 $\{1, 2, 3, 4\}$다. 문자열 $s$의 PPS 크기를 $s$의 force라고 한다.

크랩 씨는 새 무기를 시험해 보려고 문자열 $s$를 적어 두고 장전할 준비를 했다. 그런데 갑자기 몹시 피곤해져서 잠이 들었다. 깨어나 보니 문자열이 없었다. 적의 스파이인 크랩바크 씨와 바크 씨가 집에 침입해 문자열에 여러 작업을 해 두었기 때문이다.

먼저 크랩바크 씨가 도착했다. 그는 문자열을 가져가 PPS를 무작위 순서의 수열로 적었다. 이후 바크 씨가 침입해 크랩바크 씨가 적은 수 중 일부를 지웠을 수 있다.

크랩 씨는 도움이 필요하다. 문자열 $s$를 복원하고 그 force를 알려 달라. 복원할 수 있는 문자열이 여럿이므로, 가능한 force의 최솟값을 구하라.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $\ell$ ($1 \le n \le 3 \cdot 10^5$, $1 \le \ell \le 10^{18}$)이 주어진다. 각각 크랩 씨가 찾은 수열의 길이와 처음 문자열의 길이다. 둘째 줄에는 $n$개의 정수 $a_i$ ($1 \le a_i \le \ell$)가 주어진다. 모든 수는 서로 다르다.

입력의 마지막에는 "0 0"이 적힌 줄이 있다. 이 줄을 읽은 뒤에는 프로그램을 정상적으로 종료해야 한다.

모든 테스트 케이스의 $n$ 합은 $3 \cdot 10^5$을 넘지 않는다.

각 테스트 케이스마다 복원한 문자열의 force 최솟값을 한 줄에 정수 하나로 출력한다.

첫 번째 테스트 케이스에서 force가 최소인 문자열 중 하나는 "abacaba"다. 이 문자열의 PPS는 $\{1, 3, 7\}$이므로 force는 3이다.

두 번째 테스트 케이스의 문자열은 "cbcbcbcbcrab"일 수 있다. 이 문자열의 PPS는 $\{1, 3, 5, 7, 9\}$이므로 force는 5다. 이보다 작은 PPS를 갖는 문자열은 복원할 수 없음을 증명할 수 있다.

세 번째 테스트 케이스에서는 문자열 "crabbarccrabbarc"를 보자. 이 문자열의 PPS는 $\{1, 8, 16\}$이므로 force는 3이다.