## PAGAIN - Prime Again

English | Vietnamese |

In this problem, you have to find the nearest prime number smaller than N. (3 <= N <= 2^32)

### Input

The first line contains an integer T specifying the number of test cases. (T <= 10000)

T lines follow, each line contains an integer N.

### Output

For each test case, output the result on one line.

### Example

Input:3 5 10 17Output:3 7 13

Added by: | Race with time |

Date: | 2008-12-25 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |