알렉산드리아의 디오판토스

알렉산드리아의 디오판토스는 알렉산드리아에 살았던 이집트의 수학자이다. 그는 정수해만을 가지는 다항 방정식을 처음으로 연구한 수학자로, 그를 기리기 위해 이러한 방정식을 디오판토스 방정식이라 부른다.

가장 유명한 디오판토스 방정식은 $x^n + y^n = z^n$ 이다. 페르마는 $n > 2$ 일 때 정수해가 존재하지 않는다고 추측했고, 앤드루 와일스가 이를 증명하였다.

다음 디오판토스 방정식을 생각하자.

$\frac{1}{x} + \frac{1}{y} = \frac{1}{n} \qquad (x, y, n \in \mathbb{N}^+)$

$n$ 이 주어졌을 때, 이 방정식을 만족하는 해 $(x, y)$ 는 모두 몇 개인가? (단, $x \le y$ 이다.) 예를 들어 $n = 4$ 이면 아래와 같이 서로 다른 해가 정확히 3개 존재한다.

$\frac{1}{5} + \frac{1}{20} = \frac{1}{4}, \qquad \frac{1}{6} + \frac{1}{12} = \frac{1}{4}, \qquad \frac{1}{8} + \frac{1}{8} = \frac{1}{4}$

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어서 각 테스트 케이스마다 한 줄에 정수 $n$ 이 하나씩 주어진다. ($1 \le n \le 10^9$)

각 테스트 케이스마다 먼저 한 줄에 Scenario #i: 를 출력한다. 여기서 $i$ 는 1부터 시작하는 테스트 케이스의 번호이다. 그다음 줄에는 주어진 $n$ 에 대한 방정식의 해의 개수를 출력한다. 서로 다른 테스트 케이스의 출력 사이에는 빈 줄을 하나씩 넣는다.