28474번 - 피보나치 서로소

문제

피보나치 수열은 $F_n = F_{n-1} + F_{n-2} (n > 2),ドル $F_1 = F_2 = 1$을 만족하는 수열이다. $F_n$을 $n$번째 피보나치 수라고 한다.

또한 어떤 두 자연수 $a,ドル $b$가 서로소일 조건은 $gcd(a,b)=1$과 같다. ($gcd$는 최대공약수를 뜻한다.)

승은이는 피보나치 수를 매우 좋아한다. 피보나치 수를 너무 좋아한 나머지 자신의 주변 사람들에게도 피보나치 수의 아름다움을 알리려 노력한다.

그런 승은이의 뻔선 이주도 예외는 아니었다. 학교에 다니면서 승은이와 매일 마주쳐야 하는 이주는 승은이의 설교를 더 이상 들을 수 없었다.

승은이의 설교를 피하기 위해 조사를 하던 중 승은이의 약점을 하나 알아냈다. 그것은 바로 승은이가 서로소인 숫자 쌍을 보면 기겁을 하며 피한다는 것이었다.

이주는 이 사실을 알자마자 아무 서로소인 숫자 쌍을 가지고 학교에 달려가 승은이에게 보여줬지만 피보나치 수만 취급하던 승은이에게는 별 타격이 없었다.

이 사실에 낙담한 이주를 위해서 우리가 서로소인 피보나치 수의 쌍을 찾아주고자 한다. 하지만 모든 쌍을 찾기에는 무리가 있기에 1ドル$번째부터 $n-1$번째까지 피보나치 수 중에서 $n$번째 피보나치 수와 서로소인 것이 몇 개 있는지 세어주려고 한다.

이주가 승은이의 설교를 피할 수 있도록 도와주자.

입력

첫 줄에 테스트 케이스의 수 $T$가 주어진다. $( 1 \le T \le 1\ 000 )$

그 다음 줄마다 $n$번째 피보나치 수를 뜻하는 $n$이 주어진다. $( 1 \le n \le 1\ 000\ 000\ 000 )$

출력

$T$개의 줄마다 각각 $n$번째 피보나치 수와 서로소인 $i(<n)$번째 피보나치 수의 개수를 출력해라.

제한

힌트