AlgoLiga 2018

Liczba doskonała to taka, której suma dzielników właściwych jest jej równa. Do zbioru liczb doskonałych należy liczba 6, ponieważ:

D₆ = {1, 2, 3, 6}

6 = 1 + 2 + 3

lub 28:

D₂₈ = {1, 2, 4, 7, 14, 28}

28 = 1 + 2 + 4 + 7 + 14

Ciekawostką jest, że nie udało się nikomu jeszcze znaleźć nieparzystej liczby doskonałej, nawet nie istnieje na to dowód, czy jest taka. Nie wiadomo także, czy takich liczb jest nieskończenie wiele. Jednym ze sposobów szukania ich, jest określanie sum dzielników liczb w danym przedziale i badanie ich właściwości, i takie jest twoje zadanie. Dla danego przedziału [a, b], znajdź najmniejszą liczbę naturalną należącą do tego przedziału, której suma dzielników jest równa n (pod uwagę bierzemy wszystkie dzielniki naturalne danej liczby).

Uwaga! Algorytm wzorcowy oparty jest na wczytywaniu scanf'em i wypisywaniu printf'em w języku C++.

Wejście

Uwaga!!! Specyfikacja zadania różni się od zadania z XIII rundy algoligi.

W pierwszym wierszu jedna liczba naturalna t określająca liczbę zestawów danych (t < 300 001).

Każdy zestaw danych składa się z trzech liczb: a, b i n, gdzie 0 < a ≤ b ≤ 8⋅10⁶ i 0 < n ≤ 8⋅10⁶ .

Wyjście

Dla każdego zestawu szukana liczba lub napis "brak" jeśli taka liczba nie istnieje.

Przykład

Wejście:

3
2 10 3
2 10 4
2 10 5

Wyjście:

2
3
brak