Jasiu jest zapalonym hodowca królików. Ostatnio poprzez eksperymenty genetyczne uszkodził DNA jednego z królików i zauważył ze stały się nieśmiertelne oraz rozmnażają się w specyficzny sposób: jeżeli pierwszego dnia mamy "a" samców a drugiego dołączymy "b-a" samic (warto zauważyć, że drugiego dnia jest dokładnie "b" królików) , to trzeciego dnia otrzymamy a+b królików, czwartego a+2b. Jasiu doszedł to następującej prawidłowości: liczba królików w n-tym dniu jest równa sumie królików w dniach n-1 oraz n-2. Jako ze Jasiu nie był zbyt dobry z matematyki ma problem z wyliczaniem kolejnych wartości ciągu. A chciałby wszystko zweryfikować. Pomóż Jasiowi i napisz program wyliczający liczbę królików w n-tym dniu. Ale ponieważ do udowodnienia prawidłowości Jasiowi wystarcza jedynie podanie ostatnie cyfry liczby królików w n-tym dniu, wiec zostaniesz poproszony o wypisanie ostatniej cyfry.

Wejście

W pierwszej linii znajduje się dokładnie jedna liczba całkowita t (1<=t<=10000) oznaczająca liczbę zestawów danych. W t kolejnych wierszach znajdują się 3 liczby: n a b (1<=n<=2*10⁶, 1<=a,b<=5*10⁹) oznaczające odpowiednio: liczbę dni, a - liczbę królików pierwszego dnia, b - liczbę królików drugiego dnia.

Wyjście

W każdym z t wierszy wyjścia powinna znaleźć się dokładnie jedna liczba całkowita, oznaczająca ostatnią cyfrę liczby krolików w n-tym dniu.

Przykład

Wejście:
2
5 1 1
4 4 3

Wyjście:
5
0


Wytłumaczenie:
I przypadek testowy: kolejne dni: 1 1 2 3 5;
II przypadek testowy: kolejne dni: 4 3 7 10;