Problem description

Szef w jednej z dużych firm programistycznych wymyślił oryginalny sposób na wypłacanie premii pracownikom. Każdy z n pracowników może samodzielnie wybrać wysokość swojej premii jako całkowite l w zakresie od 1 do k dolarów. Jednak istnieje haczyk: jeśli wybrana przez pracownika premia l przekroczy c% średniej ze wszystkich wybranych premii, to pracownik nie otrzyma nic.

Bardziej formalnie premię l otrzymuje pracownik tylko wtedy, gdy:

$$ l \le \frac{c \cdot S}{100 \cdot n} $$

gdzie:

• l — wybrana przez pracownika premia,
• S — suma wszystkich wybranych premii,
• n — liczba pracowników,
• c — procentowy próg przyznania premii.

W przeciwnym razie premia przepada (jest równa 0).

Pracownicy szybko zorientowali się w podstępie szefa i proszą Cię o pomoc w wybraniu strategii, która pozwoli zmaksymalizować łączną sumę otrzymanych premii. Ponadto wiele firm poszło za tym przykładem i twój program powinien udzielić odpowiedzi dla q zapytań.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę naturalną q.

Następne q linii zawierają opis kolejnych zapytań

• n — liczba pracowników
• k — maksymalna wartość premii, jaką może wybrać pracownik
• c — wartość procentowa progu

Wyjście

Dla każdego zapytania wypisz jedną liczbę całkowitą — największą możliwą sumę otrzymanych premii przy optymalnym wyborze strategii przez pracowników.

Ograniczenia

• 1 ≤ q ≤ 1 000
• 2 ≤ n ≤ 100 000
• 5 ≤ k ≤ 10⁹
• 5 ≤ c ≤ 95

Suma n we wszystkich przypadkach testowych nie przekroczy 100 000.

Przykład

2
3 10 50
2 3 25

4
0