printЗадачи очного тура личного первенства

print9. Prime Polynom

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself. The first prime numbers are 2, 3, 5, 7, 11, 13, 17, … It is known that no non-constant polynomial function `P(n)` exists that evaluates to a prime number for all integers `n`. But there are some famous quadratic polynomials that are prime for all non-negative integers less than `M` (`M` depends on the polynomial).
You will be given integers `A`, `B` and `C`. You should find the smallest non-negative integer `M` such that `A*M^2\ +\ B*M\ +\ C` is not a prime number.
Constraints
  • A will be between 1 and 10000, inclusive.
  • B will be between –10000 and 10000, inclusive.
  • C will be between –10000 and 10000, inclusive.
Input contains `N` – number of polynoms, followed by `N` lines, each of these define one polynom by three integers `A` `B` `C`, separated by space character.
For each polynom output smallest non-negative integer `M` such that `A*M^2\ +\ B*M\ +\ C` is not a prime number.

Sample Input

5
1 -1 41
1 1 41
1 1 -13
1 -15 97
1 -79 1601

Sample Output

41
40
0
48
80
loading