Changlong`ів брат
Чанлонг — це гарний і розумний хлопець, якого захоплюються багато красивих дівчат. Щодня він отримує десятки тисяч листів від дівчат, які висловлюють своє палке бажання стати його супутницею життя. Ви бачите, що Чанлонг дуже втомився від цього, і одного дня він придумав ідею, як уникнути цієї турботи. Він заявляє:
Тільки ті розумні дівчата, які можуть вирішити наведену нижче задачу, мають право стати його дружиною.
Задача Чанлонга формулюється так:
Існує одна цікава послідовність чисел a_1, a_2, ..., a_n, ця послідовність має дуже привабливу властивість, що кожне число з'являється рівно p разів, за винятком певного числа t, яке зустрічається q разів. Як витягти це певне число t з цієї послідовності? Щоб зробити цю задачу більш загадковою, Чанлонг припускає, що залучені числа p, q у його задачі є взаємно простими, тобто gcd(p, q)=1.
Метод Чанлонга працює дуже добре. Після його заяви кількість отриманих листів значно зменшилася. Дівчата починають обмірковувати задачу з безперервними напруженими зусиллями, але незабаром розуміють, що ця задача перевищує їхні можливості. Тож більшість з них здаються, але є одна красива дівчина, яка наполегливо працює над цією задачею. Одного дня ця дівчина зустрічає вас і запрошує допомогти їй.
Вхідні дані
У першому рядку введення знаходиться ціле число k (0 < k ≤ 100), кількість тестових випадків.
Для кожного тестового випадку буде рядок, що містить три цілі числа: n (0 < n ≤ 10^7), p, q (1 < p, q < 200, gcd(p,q)=1) і рядок, що містить n елементів a_i (0 < a_i < 10^7) послідовності.
Вихідні дані
Для кожного тестового випадку ви повинні спочатку вивести рядок з "Case #:", де # — це id тестового випадку, потім ви повинні вивести певне число t, тобто число, яке зустрічається q разів у послідовності.