피사노 주기

1960년에 IBM에서 일하던 Donald Wall은 피보나치 수열을 $m$으로 나눈 나머지가 주기를 이룬다는 사실을 증명했다.

예를 들어 피보나치 수열의 처음 10개 항을 11로 나눈 나머지는 다음과 같다.

나머지로 만든 수열은 같은 구간을 되풀이한다. 되풀이되는 부분 수열의 길이를 $k(m)$이라고 하면 $k(11) = 10$이다.

Wall은 다음 성질도 증명했다.

• $m > 2$이면 $k(m)$은 짝수다.
• $2$보다 큰 짝수 $n$마다 $k(m) = n$인 $m$이 존재한다.
• $k(m) \le m^2 - 1$
• $k(2^n) = 3 \times 2^{n-1}$
• $k(5^n) = 4 \times 5^n$
• $k(2 \times 5^n) = 12 \times 5^n$
• $n > 2$이면 $k(10^n) = 15 \times 10^{n-1}$

$m$이 주어졌을 때 $k(m)$을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $P$가 주어진다.

다음 $P$개 줄에는 각 줄마다 정수 $N$과 $M$이 공백 하나로 구분되어 주어진다. $N$은 테스트 케이스의 번호이고, $M$은 문제에서 설명한 $m$이다.

각 테스트 케이스마다 테스트 케이스의 번호 $N$과 $k(M)$을 공백 하나로 구분해 한 줄에 출력한다. 입력에 주어진 순서를 그대로 따른다.

• $1 \le P \le 1{,}000$
• $2 \le M \le 1{,}000{,}000$
• 모든 테스트 케이스의 $k(M)$을 더한 값은 $500{,}000$ 이하다.