Treasure Chest

All submissions for this problem are available.
Thorin wanted to protect what was left of his family's wealth before he embarked on his journey to retrieve Smaug's treasure. And though he was accompanied on the quest by manyof his race, and by Gandalf, he didn't want to take any chances; he hid a number of such chests, deep underground. And then they were lost. Until, they were discovered a couple ofcenturies ago. Countless men and women have tried since, tried and failed to open any of them. Few people know this, and most of the ones who did died a long time ago, but thedwarves were exceptionally good at making treasure chests, famous for their tricky locks. Each treasure chest had two numbers written on them, hidden in the intricate carvings. Andthough the role of these two numbers has been known for decades now, no one has been able to come any closer to opening any of them for there is a third number involved which is,perhaps, the most important of all. Written in plain sight in the Khuzdûl language, it remained a mystery until now. When a group of researches finally deciphered the ancient language.
The locks require an input based on the three numbers  let's call the first two 'k' and 's'. The dwarves were obsessed with primes and a particular series wherein each term was equalto the sum of the preceding two terms. The encryption required the treasure seeker to calculate the nth number in this series and then subtractk from that. let's call the result 'x'. 'n' is the number in the Khuzdûl language. The xth prime number was then calculated and 's' subsequently subtracted from it, giving 'y'.
Thorin didn't want to make it easy, so he added another round of protection. One would have to calculate the count of numbers relatively prime to ‘y’ to arrive at the answer which needs to befed to open the chest. However, in the rare case that y does not turn out to be a valid natural number, one needs to feed in 1. Given n k s, your task is to find out the code that'll unlock the chest.
Input
t test cases. t lines follow with 3 integers separated by a space
n k s
Output
t lines, each carrying the output for the t test cases.
Note:
1. All nth and xth number calculations are 1 – indexed.
2. The series for the nth number has its first two elements 0 and 1.
Contraints
1<=t<=2000
1<= n <= 93
1<=x<=10^{8}
Example
Input:2
6 3 0
10 12 12 Output:
2
66
Author:  troika_bytes13 
Tags  troika_bytes13 
Date Added:  5022013 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 