Did you notice the maximum value of N is 10^12. There’s not enough stack space to recurse that deep.
You may want to generate the first few numbers and look up the resulting sequence on OEIS. It might give you some ideas.
Also: it’s usually easier to read and process one test case at a time. There’s no need to read the inputs and process them all before writing out the results at the end. The inputs and outputs may be interleaved when you run your program interactively, but when SPOJ runs it, the inputs will come from a file, and the outputs will go to a different file. It doesn’t matter so much when there are single number inputs and outputs like for this problem, but the data for some problems can be complex, and then, reading and processing one test case at a time is so much easier.
LOCKER