리벤지 오브 피보나치

피보나치 수열은 다음과 같이 정의된다.

• $F(0) = F(1) = 1$
• $F(n) = F(n-1) + F(n-2)$ ($n \ge 2$)

여기서 $n$을 피보나치 수 $F(n)$의 인덱스라고 부른다.

피보나치 수열은 오래전부터 많은 사람이 연구해 왔고, 지금까지 수많은 성질이 밝혀졌다. 선영이는 피보나치 수를 연구하는 것을 무척 좋아한다. 관련 논문을 많이 읽은 선영이는 이제 더 이상 새로 밝혀낼 성질이 없다고 생각했다.

그날 밤 꿈에 피보나치가 나타나 이렇게 말했다. "아직 밝혀지지 않은 중요한 성질이 남아 있다네. 예를 들면, 피보나치 수 347746739..."

선영이는 잠에서 깨어나 뒤에 이어지는 숫자를 떠올리려 했지만 기억나지 않았다. 그래서 이 수가 무엇인지 알아내는 프로그램을 작성하려고 한다.

어떤 피보나치 수의 앞부분 몇 자리가 주어졌을 때, 그 숫자들로 시작하는 피보나치 수 중 인덱스가 가장 작은 것의 인덱스를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($T \le 50{,}000$)

각 테스트 케이스는 한 줄로 이루어지며, 어떤 피보나치 수의 앞부분에 해당하는 숫자가 주어진다. 이 숫자는 최대 40자리이고, 맨 앞에 불필요한 0은 붙지 않는다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 주어진 숫자로 시작하는 피보나치 수 중 가장 작은 인덱스이다.

인덱스가 100,000보다 작은 피보나치 수 중에서 주어진 숫자로 시작하는 것이 하나도 없으면 $y$ 자리에 $-1$을 출력한다.