직사각형 집합

피타고리안 트리플은 $a^2 + b^2 = c^2$을 만족하는 양의 정수 세 개 $a$, $b$, $c$를 묶은 것이고 $(a, b, c)$로 쓴다. $x > y > 0$인 정수 $x$와 $y$를 잡아 $a = 2xy$, $b = x^2 - y^2$, $c = x^2 + y^2$로 두면 피타고리안 트리플을 만들 수 있다.

$\mathbb{R} = \{R_1, R_2, \ldots, R_i, \ldots\}$은 직사각형의 집합이다. $R_i$의 너비는 $w_i$, 높이는 $h_i$, 대각선 길이는 $d_i$이다. $\mathbb{R}$에 속한 직사각형이 모두 다음 조건을 만족하면 이 집합을 피타고리안 기초 직사각형 집합이라고 부른다.

• $(w_i, h_i, d_i)$는 피타고리안 트리플이다.
• $w_i < h_i$
• $i \neq j$이면 $\dfrac{h_i}{w_i} \neq \dfrac{h_j}{w_j}$

피타고라스 고등학교에 다니는 창영이는 길이가 $L$인 철사를 가지고 논다. 철사를 여러 조각으로 자른 뒤 각 조각을 구부려 직사각형을 하나씩 만드는데, 이렇게 만든 직사각형의 집합은 피타고리안 기초 직사각형 집합이어야 한다. $R_i$ 하나를 만드는 데 드는 철사의 길이는 $2(w_i + h_i)$이다.

직사각형 $R_i$를 너비와 높이의 쌍 $(w_i, h_i)$로 적자. $L$이 94이면 창영이는 직사각형 3개를 만들 수 있다. $\mathbb{R} = \{(3, 4), (5, 12), (8, 15)\}$가 그런 경우다. 같은 철사로 $\mathbb{R} = \{(3, 4), (7, 24)\}$를 만들면 직사각형은 2개뿐이다.

$L$이 주어졌을 때 창영이가 만들 수 있는 직사각형 개수의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 한 줄로 이루어지며, 철사의 길이 $L$이 주어진다. ($14 \le L \le 1{,}000{,}000$)

각 테스트 케이스마다 길이가 $L$인 철사로 창영이가 만들 수 있는 직사각형 개수의 최댓값을 한 줄에 출력한다.