Congruence Problem

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

Input	Output
2 3 5	2 2