Changlong's brother
Чанлонг — красивый и умный парень, который привлекает внимание множества красивых девушек. Каждый день он получает тысячи писем от девушек, желающих стать его спутницей жизни. Устав от этого, Чанлонг придумал способ избавиться от навязчивого внимания. Он заявил:
Только те умные девушки, которые смогут решить следующую задачу, могут претендовать на его руку и сердце.
Задача Чанлонга такова:
Есть интересная последовательность чисел 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 раз в последовательности.