Migrated from Lutece 933 The minimum square sum

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Given a prime $p (p<10^8)$,you are to find min{$x^2+y^2$},where $x$ and $y$ belongs to positive integer, so that $(x^2+y^2) \equiv 0$ (mod $p$).

Input

Every line is a $p$. No more than $10001$ test cases.

Output

The minimum square sum as described above.

Samples

2
3
5

2
18
5

Resources

2011 Heilongjiang collegiate programming contest