Set of Rectangles

A Pythagorean triple is three positive integers $a$, $b$, $c$ with $a^2 + b^2 = c^2$, written as $(a, b, c)$. Picking integers $x$ and $y$ with $x > y > 0$ and setting $a = 2xy$, $b = x^2 - y^2$, $c = x^2 + y^2$ produces a Pythagorean triple.

$\mathbb{R} = \{R_1, R_2, \ldots, R_i, \ldots\}$ is a set of rectangles. Rectangle $R_i$ has width $w_i$, height $h_i$, and diagonal length $d_i$. When every rectangle in $\mathbb{R}$ satisfies the conditions below, the set is called a Pythagorean base rectangle set.

• $(w_i, h_i, d_i)$ is a Pythagorean triple.
• $w_i < h_i$
• $\dfrac{h_i}{w_i} \neq \dfrac{h_j}{w_j}$ whenever $i \neq j$

Changyoung, a student at Pythagoras High School, plays with a wire of length $L$. He cuts the wire into pieces and bends each piece into one rectangle, and the set of rectangles he ends up with must be a Pythagorean base rectangle set. Making $R_i$ uses $2(w_i + h_i)$ of wire.

Write rectangle $R_i$ as the pair of width and height $(w_i, h_i)$. When $L$ is 94, Changyoung can make 3 rectangles, for instance $\mathbb{R} = \{(3, 4), (5, 12), (8, 15)\}$. Building $\mathbb{R} = \{(3, 4), (7, 24)\}$ from the same wire leaves him with only 2 rectangles.

Given $L$, write a program that finds the largest number of rectangles Changyoung can make.

The first line contains the number of test cases $T$. Each test case is a single line holding the wire length $L$. ($14 \le L \le 1{,}000{,}000$)

For each test case, print on one line the largest number of rectangles Changyoung can make from a wire of length $L$.