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

    Discussion

    Statistics


    19% Solution Ratio

    YouKnowWhoEarliest, 1M ago

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

    Related Contests