Under construction

Still being built. Things may change

Perfect Harmony (Small)

Interview

Time limit5sMemory limit512 MB

Summary
Pick the smallest frequency between L and H that divides or is divided by every given frequency, or report NO.
Level

Easy3 of 10

Topics
Number theory, Brute force
Solved
No attempts yet

Problem

Jeff plays in the great Atlantean orchestra. Every player has already decided which sound to play, and for simplicity each player plays exactly one sound. Two sounds are in harmony when the frequency of one of them divides the frequency of the other. That is a restrictive idea of harmony, but the Atlanteans are known to be conservative about music. The notes chosen by the other players are not necessarily in harmony with each other. Jeff wants his own note to improve the symphony, so he wants to choose a note that is in harmony with the notes of all the other players.

This sounds simple. All the frequencies are positive integers, so Jeff could play the note with frequency 1, or, from the other side, the least common multiple of all the other notes. Unfortunately Jeff's instrument covers only a limited range of notes. Decide whether Jeff can play a note that is in harmony with all the others.

Input

The first line contains the number of test cases TT. TT test cases follow, and each test case is described by two lines. The first line contains three integers NN, LL and HH, where NN is the number of other players and LL and HH are the lowest and the highest frequency Jeff's instrument can play. The second line contains the NN frequencies of the notes played by the other players.

Limits

  • 1≤T≤401 \le T \le 40
  • 1≤N≤1001 \le N \le 100
  • 1≤L≤H≤100001 \le L \le H \le 10000
  • Every frequency is a positive integer no larger than 10000.

Output

For each test case, print one line in the form Case #x: y. Here xx is the case number starting from 1, and yy is either the string NO when Jeff cannot play an appropriate note, or a frequency he can play. When several frequencies work, print the lowest one.

Examples1

  1. Example 1

    Input
    2
    3 2 100
    3 5 7
    4 8 16
    1 20 5 2
    
    Expected output
    Case #1: NO
    Case #2: 10