Fermat's last theorem (3) P94857

Statement

thehtml

This is another exercise about Fermat’s last theorem, which was explained in the exercise ‍

Write a program that, given four natural numbers a,b,c,d with a≤ b and c≤ d, prints the number of solutions to the equation

x² + y² = z²

such that a ≤ x ≤ b and c ≤ y ≤ d.

Input

Input has several cases. Each case consists of four natural numbers a, b, c, d such that a≤ b and c≤ d.

Output

For every case, print in a line the number of solutions to the equation

x² + y² = z²

that fulfill a ≤ x ≤ b and c ≤ y ≤ d.

Public test cases

Input

2 5 4 13
1 1 2 3

Output

2
0

Information