I. Hello Hello Infinite Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Essam has recently discovered his love for arithmetic progressions. Today, he chose three positive integers $$$n$$$, $$$k$$$, and $$$l$$$.

He grabbed a marker and wrote two separate sequences on his whiteboard:

  1. The first $$$n$$$ multiples of $$$k$$$: $$$1 \cdot k, 2 \cdot k, 3 \cdot k, \dots, n \cdot k$$$.
  2. The first $$$n$$$ multiples of $$$l$$$: $$$1 \cdot l, 2 \cdot l, 3 \cdot l, \dots, n \cdot l$$$.

Essam is only interested in even numbers. He wants to find the total number of even integers written on his whiteboard across both sequences. If a number appears in both sequences, Essam writes it twice, and it should be counted twice. Given $$$n$$$, $$$k$$$, and $$$l$$$, help Essam find the total number of even integers.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The only line of each test case contains three integers $$$n$$$, $$$k$$$, and $$$l$$$ ($$$1 \le n, k, l \le 10^9$$$).

Output

For each test case, output a single integer — the total number of even integers written on the whiteboard.

Example
Input
3
4 2 3
5 3 5
10 4 6
Output
6
4
20