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

输入格式

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

输出格式

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

说明

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

样例

样例输入 1

3
5 4 3
2 2 2
8 1 5

样例输出 1

4
1
24

样例输入 2

2
500000003 1 600000010
511374200 637192506 100000000

样例输出 2

799999999
7