Sutomo 1 P2S1 Programming Contest

Arta senang belajar matematika. Pada suatu hari, Acek, guru matematika Arta, baru mengajari Arta pembagian. Acek langsung memberi Arta sebuah soal matematika. Diberikan bilangan bulat positif N, A dan B, berapa banyak bilangan bulat antara 1..N yang habis dibagi A atau B? Arta kaget dan langsung meminta bantuan anda untuk menyelesaikan masalahnya.

Input

Baris pertama terdiri dari sebuah bilangan bulat S(1 <= S <= 50) yang menyatakan banyaknya soal yang diberikan Acek. Tiap soal terdiri dari dua baris, baris pertama berisi bilangan bulat N(1 <= N <= 5000) dan baris kedua berisi dua bilangan bulat A dan B(1<= A, B <= 5000).

Output

Keluarkan S baris bilangan bulat yang masing-masing merupakan jawaban dari soal-soal Acek dimulai dari baris pertama yaitu jawaban untuk soal pertama Acek dan seterusnya sampai baris terakhir yang merupakan jawaban untuk soal terakhir Acek.

Example

Input:
3
10
2 3
25
4 6
100
4 6

Output:
7
8
33