두 수 a, b (1 <= a <= b, 1 < b)가 주어질 때 최대공약수를 구하는 함수 gcd는 다음과 같다.

int gcd(int a,int b) {
    if( b%a == 0 )
        return a;
    else
        return gcd(b%a,a);
}

예를 들어 gcd(9, 15)는 재귀함수가 총 3번 호출된다.

gcd(9, 15) -> gcd(6, 9) -> gcd(3, 6)

피에로는 모든 i, j 쌍에 대해 (1 <= i <= j, 1 < j) gcd(i,j)의 최대 호출 횟수가 궁금하다.

n이 주어질 때, i, j <= n 을 만족하는 모든 i, j 쌍들 중 호출되는 재귀함수의 최대 수를 구해서 출력하자.

입력

• 첫 번째 줄에는 가능한 테스트케이스의 수 T가 주어진다. (T <= 20)
• 이 후 각 T줄에 대하여 n이 주어진다. (1 <= n <= 1,000,000)

출력

입출력 예

입력

3
3
7
10

출력

2
3
4

입출력 보충

gcd(i,j) 함수가 호출되는 경우는 1 <= i <= j, 1 < j 가 성립할때입니다.
gcd(3,2) 와 같이 위의 i,j 값이 성립하지 않는 경우는 "세지" 않습니다.

출처:Fate