CERI2018D - Largest prime factor


The task is to print the largest prime factor of an integer.

Input

The first line of the input consist of a single integer number t which determines the number of tests.

In each of next t lines there is a single integer number n.

Constraints

  • 0 < t ≤ 1000
  • 1 < n ≤ 1 000 000 000

Output

Print the largest prime factor of n

Example

Input:
3
10
11
12
Output:
5
11
3

hide comments
julkas: 2019-06-30 14:07:13

Last edit: 2019-07-03 09:42:40
julkas: 2018-09-29 15:52:17

@Francky What is your Python2/3/PyPy total time?
=(Francky)=> I only submit a simple Ω (n²) Py3 code, it lasts in 0.01+0.02+0.04+0.50=0.57s. Zero trick inside. Edit : My Py3 code from FACT* ends in 0.08s (total time) here.
<== Thanks l

Last edit: 2018-09-30 18:11:58

Added by:Francky
Date:2018-05-03
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All