## 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 12Output:5 11 3

Added by: | Francky |

Date: | 2018-05-03 |

Time limit: | 1s-3s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |