Congruence Problem

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

Sample

InputOutput
2
3
5

2
2

Submit

Login to submit.

Statistics

19% Solution Ratio
YouKnowWhoEarliest, Jan '21
shefinFastest, 0.1s
NirjhorLightest, 393 kB
yeahmymanShortest, 462B
Toph uses cookies. By continuing you agree to our Cookie Policy.