Find the number of integer solutions of $ x^2 + 4x + 3 ≡ 0 $ $ (\text{mod } $ $m) $ where $ 0 \leq x < m $.
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.
For each testcase, print the number of solutions of the given equation.
| Input | Output |
|---|---|
2 3 5 | 2 2 |