题目描述

你正在建造一个新的太阳能农场。允许建造的区域是一个半径为 $r$ 的圆形场地，而每块太阳能电池板占据一个大小为 $w \times h$ 的矩形空间。你必须将所有电池板按照你选择的同一方向排列成一个单一的矩形阵列（即所有电池板组合起来恰好形成一个完整的矩形）。在这个农场中，最多可以放置多少块电池板？

输入格式

第一行输入包含一个整数 $T$（$1 \leq T \leq 1\,000$），表示测试用例的数量。

接下来的 $T$ 行每行代表一个测试用例，包含三个用空格分隔的整数 $r$、$w$ 和 $h$（$1 \leq r, w, h \leq 10^9$），分别表示场地的半径、每块太阳能电池板的宽度和高度。

输出格式

对于每个测试用例，输出一行，包含一个整数：在圆形场地内可以放置的太阳能电池板的最大数量。

输入输出样例 #1

输入 #1

3
5 4 3
2 2 2
8 1 5

输出 #1

4
1
24

输入输出样例 #2

输入 #2

2
500000003 1 600000010
511374200 637192506 100000000

输出 #2

799999999
7

说明/提示

下图展示了样例输入 1 中三个测试用例（从左到右）各自的一种最优太阳能电池板布局。