题目描述

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: $N$, $L$ 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.

输出格式

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.

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

Case #1: NO
Case #2: 10

提示

Limits

• $1 \leq T \leq 40$.

Small dataset (8 Pts, Test set 1 - Visible)

• $1 \leq N \leq 100$.
• $1 \leq L \leq H \leq 10000$.
• All the frequencies are no larger than $10000$.
• Time limit: 30 3 seconds.

Large dataset (35 Pts, Test set 2 - Hidden)

• $1 \leq N \leq 10^4$.
• $1 \leq L \leq H \leq 10^{16}$
• All the frequencies are no larger than $10^{16}$
• Time limit: 60 6 seconds.