Prime number

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem 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=0 (mod p).

Input

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

Output

 The minimum square sum as described above.

Sample Input

2

Sample Output

2

Hint

 

Source

HDU shadow95