FIBFACT - Fibonacci Factor

no tags 

Let F(n) be nth Fibonacci number. F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3 and so on. Given a positive integer n > 2, print the smallest prime number P such that P divides F(n) but it does not divide any F(k) smaller than F(n). Maximum value of n is limited by P where P < 2^64. You should print IMPOSSIBLE if no such P exists.

Input

First line of input contains a single positive integer T denoting number of test cases. T <= 20. Next T lines contains value of n.

Output

Output value of P corresponding to each n in separate lines.

Example

Input:
2
3
8

Output:
2
7

PS : Source Code Limit changed to 700B.


hide comments
Mitch Schwartz: 2015-03-04 00:38:21

@B Soma Naik: 3 <= n <= n_max, where n_max is chosen such that all n in the range have answers that are less than 2^64, and n_max is as large as possible.

Soma: 2015-03-03 23:14:44

can some one explain me the limit on N. i am not able to understand what is written in the question.

Jay H. Bosamiya: 2014-02-07 19:00:59

"You should print IMPOSSIBLE if no such P exists" caused a WA for me first... :(

raman sharma: 2013-01-20 11:31:27

what about n
Re( Author ) : "Maximum value of n is limited by P where P < 2^64"

Last edit: 2013-01-27 15:17:06
:D: 2011-02-25 23:49:42

On the limit on N. if the answer for M would be bigger than 2^64 then MAX_N<M. It means that there are N bigger than M with smaller solutions but there are not present in test cases.

Last edit: 2010-11-27 14:32:45

Added by:XeRoN!X
Date:2010-10-19
Time limit:3.576s
Source limit:700B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All