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 x2+4x+30 x^2 + 4x + 3 ≡ 0 (mod  (\text{mod } m)m) where 0x<m 0 \leq x < m .

Input

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

Each test case will consist of an integer m(1<m988244353) 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

Discussion

Statistics


19% Solution Ratio

YouKnowWhoEarliest, Jan '21

shefinFastest, 0.1s

NirjhorLightest, 393 kB

yeahmymanShortest, 462B

Submit

Login to submit

Editorial

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

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.