This page is still under construction.

Parts of this page are still being built. What you see may change.

Odd Area Lattice Squares

Time limit5sMemory limit256 MB

Summary
You count every lattice square with odd area that fits inside each m by n grid.
Level

Medium7 of 10

Topics
Combinatorics, Math, Geometry
Solved
No attempts yet

Problem

A lattice square is a square whose four vertices all lie on lattice points. A lattice point is a point whose xx coordinate and yy coordinate are both integers. For example, (1,5)(1, 5) is a lattice point and (1,1.5)(1, 1.5) is not.

An m×nm \times n grid is mm cells wide and nn cells tall. Its lattice points are the integer points (x,y)(x, y) with 0≤x≤m0 \le x \le m and 0≤y≤n0 \le y \le n.

Some lattice squares that fit in the grid have sides parallel to the axes, and others are tilted. If one side of a lattice square is the vector (p,q)(p, q), the square has area p2+q2p^2 + q^2, so a tilted square also has an integer area. The square built on (1,2)(1, 2) has area 55, which is odd, and the square built on (1,1)(1, 1) has area 22, which is even.

Given the size of the grid, count the lattice squares that fit in the grid and have odd area.

Two lattice squares are different unless they share all four sides.

Input

The input has at most 50000 lines. Each line contains two integers mm and nn, the size of the grid (1≤m,n≤1000001 \le m, n \le 100000).

The last line contains two zeros. That line is not processed.

Output

For each grid, print the number of lattice squares with odd area, one per line. The answer always fits in a 64-bit signed integer.

Examples1

  1. Example 1

    Input
    2 2
    3 3
    4 4
    0 0
    
    Expected output
    4
    12
    28