많은 어플리케이션은 매우 큰 수를 사용한다. 이러한 어플리케이션은 데이터를 안전하게 전송하고, 암호화하기 위해서 수를 키로 사용한다.

수가 주어지면, 그 수의 팩토리얼의 자리수를 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 테스트 케이스의 수가 주어진다. 다음 줄부터 한 줄에 하나씩 정수 m이 주어진다. (1 ≤ m ≤ 10⁷)

출력 형식

입력으로 주어지는 수 m마다 m!의 길이를 출력한다.

예제 입력

2
10
20

예제 출력

7
19