# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Congruence Problem

By jackal_1586 · 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.

## Sample

InputOutput
2
3
5


2
2


### Statistics

19% Solution Ratio

YouKnowWhoEarliest, 1M ago

shefinFastest, 0.1s

NirjhorLightest, 393 kB

yeahmymanShortest, 462B

### Editorial

Let y = x + 2 (1). Then x2 + 4x + 3 ≡ 0 (mod m) (2) becomes y2 ≡ 1 (mod m) (3). Since (1) is a bije...

### Related Contests

 Criterion 2021 Round 8Ended 1M ago