Visible Lattice

Time limit1sMemory limit512 MB

Summary
Count lattice points in an N x N x N grid visible from the origin, meaning no other lattice point lies on the segment to them.
Level

Medium7 of 10

Topics
Math, Number theory, Combinatorics, Dynamic programming
Solved
No attempts yet

Problem

Consider an N × N × N lattice. One corner is at (0,0,0) and the opposite one is at (N, N, N). How many lattice points are visible from the corner at (0,0,0)? A point X is visible from a point Y iff no other lattice point lies on the segment joining X and Y.

Input

The first line contains the number of test cases T. The next T lines each contain a single integer N.

Output

Output T lines, one corresponding to each test case.

Constraints

  • T ≤ 100, 1 ≤ N ≤ 100

Examples1

  1. Example 1

    Input
    3
1
2
5
    Expected output
    7
19
175