시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 512 MB105221826.087%

문제

Jeff is a part of the great Atlantean orchestra. Each player of the orchestra has already decided what sound will he play (for the sake of simplicity we assume each player plays only one sound). We say two sounds are in harmony if the frequency of any one of them divides the frequency of the other (that's a pretty restrictive idea of harmony, but the Atlanteans are known to be very conservative in music). Jeff knows that the notes played by other players are not necessarily in harmony with each other. He wants his own note to improve the symphony, so he wants to choose his note so that it is in harmony with the notes all the other players play.

Now, this sounds simple (as all the frequencies are positive integers, it would be enough for Jeff to play the note with frequency 1, or, from the other side, the Least Common Multiple of all the other notes), but unfortunately Jeff's instrument has only a limited range of notes available. Help Jeff find out if playing a note harmonious with all others is possible.

입력

The first line of the input gives the number of test cases, T.  T test cases follow. Each test case is described by two lines. The first contains three numbers: NL and H, denoting the number of other players, the lowest and the highest note Jeff's instrument can play. The second line contains N integers denoting the frequencies of notes played by the other players.

Limits

  • 1 ≤ T ≤ 40.
  • 1 ≤ N ≤ 104.
  • 1 ≤ L ≤ H ≤ 1016
  • All the frequencies are no larger than 1016

출력

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either the string "NO" (if Jeff cannot play an appropriate note), or a possible frequency. If there are multiple frequencies Jeff could play, output the lowest one.

예제 입력 1

2
3 2 100
3 5 7
4 8 16
1 20 5 2

예제 출력 1

Case #1: NO
Case #2: 10

출처

Contest > Google > Code Jam > Google Code Jam 2011 > Round 1C C2번

채점 및 기타 정보

  • 예제는 채점하지 않는다.