트리

# 제목 설명

노드가 있는 루트 트리의 가능한 형태 개수를 구하는 정수 $n$를 지정합니다.

# 형식 입력

첫 번째 행에 음수가 아닌 정수 $t$는 $t$그룹 데이터가 있음을 나타냅니다.

다음 $t$행, 행당 정수 $n$.

# 출력 형식

총 $t$행, 행당 정수, 가능한 형태 개수를 구합니다.

대답이 더 클 수 있으므로 $10 ^ 9 + 9$의 샘플링 값을 출력해야 합니다.

일
삼

구

일
323

283888610

# 데이터 범위

모든 데이터의 경우:

$t \le 10^4$

$n \le 10^9$

# 힌트

분홍색 노드는 루트입니다.

예제 1: