FIBFACT - Fibonacci Factor
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
|
|
: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 |
RSS