410650: GYM104069 B Best University ID

The semester just started, and the University of São Paulo is welcoming its newcomers. Every new student receives a number, the university id, a number to memorize besides the phone, government id, social security, etc. Jiang Fábio Zhi, a born mathematician, wants to understand how the university ids are assigned. It is clearly not sequential nor follows alphabetic order. "Like every hard math problem, the answer must be something related to number theory!" - Jing thought. However, he doesn't know much about it and asks for the help of Enrique Byakko Junchaya, the all-knowing.

After putting in a lot of work, they notice a pattern related to prime numbers. However, to prove their theory, they need some data. Both are very good at math but not at coding. They asked for your help. Given a list of names and university ids, you must find the student with the largest prime factor in their university id. In case of a tie, print the name that appears earlier in the list.

The first line has a single integer $$$n\ (1 \leq n \leq 10^5)$$$, the number of students. The next $$$n$$$ lines contain a description of each student. First, there is a string $$$s_i\ (1\leq \vert s_i \vert \leq 20)$$$, consisting of lowercase Latin characters, the name of the student. Then a number $$$a_i\ (2 \leq a_i \leq 10^8)$$$, the university id. All names are distinct.

Print a single string, the name of the student with the largest prime factor in their university id. In case of a tie, print the one that appears earlier in the input.

5
arrais 2
cassio 3
joao 5
wang 7
mori 11

mori

4
caiaffa 97
antonio 223
matheus 21631
gustavo 384

antonio

5
jiang 99999931
nathan 99999941
germano 99999959
noronha 99999971
byakko 99999989

byakko

On the first testcase e $$$21631 = 97 \times 223$$$ and $$$384 = 2^7 \times 3$$$. Then, the student with the largest prime in the university id that appears first in the list is antonio.