python - One test case fails due to runtime error -

i trying project euler problem 25 on hackerrank.

i attempted brute force method using binet's formula.

import math  _ in range(int(input())):     numlen = int(input())     x in range(1, 5000):         fib = 1/pow(5,.5)*(pow(((1+pow(5,.5))/2),x) - pow(((1-pow(5,.5))/2),x))         if(numlen == len(str(int(fib)))):             print(x)             break 

here 5000 arbitrary number based on assumption input not more , problem not here runtime error i'm think because it's exceeding integer range(not sure).

it calculates other test cases in less 0.25 seconds.

i did searching , found this.

but recurrence method:

import math  _ in range(int(input())):     = 1     b = 0     n = int(input())     term = 1     while len(str(a)) != n:         a, b = a+b,         term+=1     print (term)  

gives timeout exceeds 10 seconds.

can please me find way improve first method , optimize second method.

note: tried storing pow() values in variables instead of recomputing , of not help.

just use second approach in example instead of computing value separately every line in input compute values 1...5000 once , cache them:

res = [0] = 0 b = 1 term = 1  while len(res) <= 5000:     a, b = b, + b     if len(str(a)) >= len(res):         res.append(term)     term += 1  print('\n'.join(str(res[int(input())]) _ in range(int(input())))) 

for input 2 3 4 produce expected output 12 17. on machine precomputing values takes 3 seconds.