# Congruence Problem

Criterion 2021 Round 8
Limits 1s, 512 MB

Find the number of integer solutions of $x^2 + 4x + 3 ≡ 0$ $(\text{mod }$ $m)$ where $0 \leq x < m$.

## Input

Input will consist of multiple test cases. The first line will contain an integer $T (1 \leq T \leq 10^5)$, the number of test cases.

Each test case will consist of an integer $m (1 < m \le 988244353)$ separated by newline.

## Output

For each testcase, print the number of solutions of the given equation.

InputOutput
2
3
5

2
2