PCPC12J - Amr Samir

no tags 

Amr started to learn division. So he gave a list of numbers to his friend and asked him to find all the divisors of each number in the given list. Now Amr has a new list of numbers containing all divisors of his original list.

As Amr loves playing with numbers, he now thinks about the repeated numbers in the new list of divisors. However this time Amr is interested in the luckiest divisor!

Lucky divisor is defined by Amr as follows: a divisor D is lucky if D divides f, where f is the frequency of this number D in the new list. Obviously f must be greater than zero.

The luckiest divisor is the divisor D that divides f where f is the maximum and D is the smallest one.

Since Amr is too lazy to write a program that solves this problem, he decided to submit it to the PCPC chief judge to put it as a problem for the teams to write a solution to it. Can you write this program for Amr?

Input

The first line contains a positive integer t <= 100, then follow t test cases. Each test case start with a line containing a single positive integer n <= 10000 number of divisors in Amr’s new list, then follows n positive integers a1, ai, ... an (ai <= 100).

Output

Your code should print an integer for each test case representing the luckiest divisor or -1 if there is no lucky divisor.

Sample

Input
2
5
2 2 3 3 3
7
2 2 2 2 3 3 3

Output
3
2

hide comments
Aman Agarwal: 2015-05-27 22:38:44

Easy one
;)

Rohit: 2015-05-22 07:35:22

Two comments on how the problem has been worded:
a) "The luckiest divisor is the divisor D that divides f where f is the maximum and D is the smallest one" is ambiguous. Please change it to "The luckiest divisor is the divisor D that divides f where f is the maximum. If two or more divisors have the same (maximum) value of f, the luckiest divisor is the one with the minimum value of D".

b) I got one WA because I ignored to count "1" in the divisors list. Mathematically, 1 is always a divisor to any positive integer and is ALWAYS ignored during prime factorization. It would be great to see either the test cases changed to not include 1 as a divisor or the wording of the problem statement changed to explicitly mention that 1 is considered to be a divisor in the input test cases.

Thanks!

Vicky: 2015-05-18 15:23:38

finally done ;)

:.Mohib.:: 2015-01-02 12:52:15

Simple One.... :)

Rishav Goyal: 2014-06-20 21:42:13

Cake walk suits the best to this problem.!!

Devesh Kumar: 2014-05-08 12:14:48

Note : given list is the list of divisor you need to work on. It caused me 5 WA

Bhavik: 2013-12-16 12:45:03

finally got it:))read question very carefully!!!!!!!!!!

Martijn Muijsers: 2013-10-22 21:38:54

"then follows n positive integers a1, ai, …an (ai<= 100)" -> "positive"

karan_dev: 2013-08-29 15:43:30

what if a[i] is 0 ?
Like for test case:-
5
0 0 0 2 2
what will be the output ?

Last edit: 2013-08-29 15:51:17
ABHISHEK KUMAR: 2013-07-23 12:41:18

got it

Last edit: 2013-07-23 14:13:51

Added by:abdelkarim
Date:2012-12-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:The First Palestinian Collegiate Programming Contest