Dla zadanych trzech niewspółliniowych punktów, określ jaka będzie długość promienia okręgu przechodzącego przez te punkty.
W pierwszym i jedynym wierszu sześć liczb całkowitych xA, yA, xB, yB, xC, yC będących współrzędnymi punktów A, B oraz C i należących do przedziału:[-1000; 1000].
Jedna liczba określająca długość promienia zaokrąglona do dwóch miejsc po przecinku.
Wejście: 0 0 3 0 3 4 Wyjście: 2.50
Bajtek bardzo chce od następnego roku pójść do przedszkola z kierunkiem rozszerzonego nauczania programowania. Poza możliwością rozwijania swoich umiejętności w najważniejszej dziedzinie życia Bajtkiem kieruje również chęć poznania pięknej pani przedszkolanki. Jednak aby się tam dostać chłopiec musi rozwiązać zagadkę, z którą mierzył się każdy 3-latek:
Jeżeli:
104 = 1
106 = 2
112 = 0
136 = 1
148 = ?
Jako starszy brat Bajtka musisz napisać program, który rozwiąże jego problem i pomoże ci poznać piękną panią przedszkolankę.
W pierwszym wierszu jedna liczba n określająca ilość testów (0<n<101). Każdy test zawiera ciąg składający się z 6 liczb: k1, k2, ..., k6 (0 ≤ ki ≤ 999 oraz 1 ≤ i ≤ 6).
Dla każdego ciągu wybierz najmniejszą i największą liczbę, a następnie wypisz odpowiadającą jej według wzoru zagadki wartość.
Wejście:
2
2 800 491 256 321 123
8 100 121 211 432 234
Wyjście:
0 4
2 0
Na ostatnim sprawdzianie z matematyki Jasio dostał ocenę bardzo dobrą i z tego powodu był bardzo niezadowolony. Okazało się, że w ostatnim zadaniu nie wyciągnął maksymalnej liczby przed znak pierwiastka, za co srogi nauczyciel odjął mu jeden punkt i nie postawił oceny celującej. Od tej chwili nasz młody bohater postanowił już nigdy nie popełnić tego błędu. Ty też nie popełnij takiego błędu na maturze i napisz program, który będzie wyciągał maksymalną liczbę całkowitą przed znak pierwiastka.
W pierwszym wierszu liczba t określająca ilość zestawów danych (0 < t < 105). Każdy zestaw składa się z dwóch liczb całkowitych a i s, gdzie a to liczba znajdująca się pod pierwiastkiem oraz s to stopień pierwiastka (0 < a < 109) oraz (1< s < 11).
Dla każdego zestawu dwie liczby całkowite. Pierwsza z nich to liczba, która będzie stała przed znakiem pierwiastka, natomiast druga to liczba stojąca pod pierwiastkiem.
Wejście:
4 4 2 8 2 7 3 24 3
Wyjście:
2 1
2 2
1 7
2 3
Istnieje pewien szyfr, którego działanie jest oparte na tablicy, składającej się z 26 kolumn i 26 wierszy wypełnionych literami.
Pierwszy wiersz zaczyna się od A i kończy na Z (A,B,C,...,Z - alfabet angielski),
pierwsza kolumna składa się z tych samych liter w tej samej kolejności.
Czytając litery z tablicy w prawą stronę lub w dół, zawsze będziemy odczytywali alfabet angielski w kolejności (możliwe są przeskoki z litery Z na literę A).
Twoim zadaniem będzie zaszyfrować podaną wiadomość, skłądającą się z ciągu dużych liter alfabetu angielskiego tym szyfrem.
Na wejście zostanie podane słowo-klucz oraz ciąg liter do zaszyfrowania.
Szyfr działa w następujący sposób:
Załóżmy, że nasz ciąg liter wygląda następująco: TO ZADANIE NIE JEST TRUDNE, a słowo-klucz: SZYFR.
Ze słowa klucza musimy ułożyć ciąg liter o tej samej długości, co ciąg
który będziemy musieli zaszyfrować (Słowo-klucz może być dłuższe od wiadomości). Wygląda to w następujący sposób:
TO ZADANIE NIE JEST TRUDNE
SZ YFRSZYF RSZ YFRS ZYFRSZ
Dzięki takiemu układowi otrzymujemy współrzędne liter z tablicy, które podstawimy za litery z właściwej wiadomości. Współrzędne pierwszej litery to (T,S), drugiej (O,Z),trzeciej (Z,Y) itd...
Szyfrując wiadomość trzeba pamiętać o zachowaniu spacji pomiędzy słowami.
Wejście
W pierwszym wierszu podana zostanie liczba t (t<=1001), która określa ilość zestawów danych.
Jeden zestaw danych składa się z dwóch wierszy. W pierwszym słowo-klucz (jeden wyraz),
zaś w drugim wiadomość - ciąg wyrazów oddzielonych spacjami lub pojedynczy wyraz, który należy zaszyfrować według klucza.
Słowo-klucz jak i wiadomość zawierają maksymalnie 10001 znaków.
Wyjście
t wierszy, w każdym zaszyfrowana wiadomość.
Przykład:
Wejście
3
KOT
ALA MA KOTA
TOK
BOLEK I LOLEK
RAK
SZYFROWANIE
Wyjście
KZT WO DYHT
UCVXY S ECVXY
JZIWRYNAXZE
Na pewnej planecie, której nazwy nie pamiętam, rozróżniamy dwa rodzaje żyjątek: Zera i Jedynki. Na początku było ich bardzo dużo. Tylko Jedynki są zdolne do rodzenia swoich potomków i mogą to robić nawet w sytuacji, gdy nie mają partnera czyli Zera do pary (jedynki mają tylko jednego potomka przez całe swoje życie), ale wtedy rodzi się tylko żyjątko płci Zero. Jeśli natomiast Jedynka ma partnera, to w takiej sytuacji rodzi się następna Jedynka. Twoim zadaniem jest określenie, ilu wszystkich przodków swojej płci ma Zero urodzone w n-tym pokoleniu. Przyjmujemy, że pierwsi przodkowie to pokolenie numer0.
W pierwszym wierszu jedna niewielka liczba określająca ilość zestawów danych (nie więcej niż 100 000).
Każdy zestaw składa się z jednej liczby n, przedstawiającą numer pokolenia Zera (0 ≤ n ≤ 100000).
Dla każdego zestawu liczba przodków żyjątka płci Zero urodzonego w n-tym pokoleniu, które są także Zerami. Wynik przedstaw modulo 1010101010101.
Wejście:
2
3
5
Wyjście:
2
7
Wskaźnik masy ciała
Na lekcji biologii klasa Bajtka uczyła się o wskaźniku masy ciała, tzw. BMI, który klasyfikuje daną osobę w jednym z zakresów wartości: niedowadze, wartości prawidłowej oraz nadwadze. Pani od biologii podała klasie wzór:
BMI=masa[kg]/(wzrost)^2[m^2]
Natomiast zakres wygląda następująco:
< 18,5 – niedowaga
[18,5; 25) – wartość prawidłowa
≥ 25,0 – nadwaga
Klasyfikacja ta nie może być stosowana u dzieci, więc Bajtek nie może wyliczyć wartości dla siebie. Postanowił więc, że napisze program, który określi w jakim zakresie znajduje się badana osoba, a Ty jako dobry kolega Bajkta, mu w tym pomożesz. Bajtek zebrał chętnych, którzy podali mu swoje dane.
W pierwszym wierszu jedna liczba t (1 ≤ t ≤ 100) określająca ilość badanych osób. W kolejnych t wierszach - imię, masa i wzrost osoby podane odpowiednio w kilogramach i centymetrach (imię - maksymalnie 20 znaków, masa i wzrost to wartości naturalne dodatnie nie przekraczające 200).
Napis: "niedowaga", następnie w osobnych liniach wypisane imiona osób z tej grupy, podobnie z grupami: "wartosc prawidlowa" oraz "nadwaga". Dane osób wypisujemy w kolejności wczytania. Wstawienie znaku końca linii po każdej grupie jest opcjonalny.
Wejście: 5 Ala 50 173 Beata 70 190 Boleslaw 100 180 Wincent 85 186 Hiacynta 62 164 Wyjście: niedowaga Ala wartosc prawidlowa Beata Wincent Hiacynta nadwaga Boleslaw
Dziś profesor Algobit będzie robił obiad. Poszedł więc do sklepu, zakupił produkty, między innymi także ziemniaki. Poprosił więc panią ekspedientkę o kilogram. Ona zapakowała mu w reklamówkę i zapytała czy 1,2 kg może być, na co profesor odpowiedział, że to jest za dużo. Pani odłożyła trzy ziemniaki i okazało się, że po zważeniu waga pokazała 980 g. Profesor stwierdził, że to jest za mało i chce dokładnie 1 kg. Pani Ania (tak miała na imię ekspedientka) nieco podirytowana stwierdziła, że nie da się dokładnie wyważyć 1 kg ziemniaków. Na to profesor popatrzył na ziemniaki i z uśmiechem na twarzy oznajmił, że da się to zrobić na dokładnie sześć sposobów.
Zakładamy, że dwa ziemniaki o tej samej wadze to dwa różne ziemniaki. Twoim zadaniem jest sprawdzenie, czy profesor ma rację.
W pierwszym wierszu n określająca liczbę ziemniaków, jakie bierzemy pod uwagę (liczba ta jest nie większa niż 1000).
W drugim wierszu n liczb całkowitych, określających wagi kolejnych ziemniaków (0 < n < 501).
Następnie jedna liczba q, określająca liczbę zapytań (q < 10 000).
Każde zapytanie jest wagą o wartości k, jaką profesor chce uzyskać nakładając ziemniaki (0 < k < 2 000 001).
Dla każdego zapytania liczba sposobów uzyskania żądanej przez profesora wagi modulo 109 + 9.
Wejście: 5 100 100 200 100 200 3 200 400 300 Wyjście: 5 7 7 Wyjaśnienie Dla rozróżnienia ziemniaków ponumerujmy kolejne wagi: 1001, 1002, 2001, 1003, 2002 Liczbę 200 możemy przedstawić jako: {1001+1002}, {1001+1003}, {1002+1003}, {2001}, {2002}. Liczbę 400 możemy przedstawić jako: {1001+1002+2001}, {1001+1003+2001}, {1002+1003+2001}, {1001+1002+2002}, {1001+1003+2002}, {1002+1003+2002}, {2001+2002}
Bitek dopiero poznaje tajniki tworzenia stron WWW, a jego wuj Bajtosław bardzo mu w tym pomaga. Dziś mają za zadanie stworzyć witrynę obsługującą sklep internetowy. Jak zwykle obaj webmasterzy dzielą się pracą. Bitek zajmuje się częścią programistyczną, zaś jego wuj częścią wizualną. Najtrudniejszą rzeczą będzie zaimplementowanie formularza kontaktowego, w którym nasz bohater musi stworzyć walidację adresu e-mail - nie wie jeszcze, że HTML 5 ma wbudowany mechanizm walidacji adresów mailowych. Czasu jest niewiele, a Bitek ma spore problemy, żeby to poprawnie zaprogramować - szczególnie dlatego, że musi używać języka PHP. Pomóż naszemu bohaterowi i napisz program w dowolnym języku sprawdzający poprawność adresu e-mail. Oto kryteria:
adres e-mail powinien
W pierwszym wierszu jedna liczba t określająca liczbę zestawów danych.
Każdy zestaw składa się z jednego wiersza, w którym mogą wystąpić znaki ASCII z przedziału [32..126]. Długość wiersza nie przekracza 100 znaków. Na początku i końcu każdego wiersza nie występują spacje.
Dla każdego zestawu testowego napis Tak, jeśli adres e-mail jest prawidłowy oraz Nie w przeciwnym razie.
Wejście: 5 mat h@edu.pl algorytm@edu.pl algoliga@algoliga.edu.pl 1234@123.PL 1234@123..pl Wyjście: Nie Tak Tak Tak Nie
Napisz program, który sprawdzi, czy dana wartość wystąpiła co najmniej trzy razy w posortowanym ciągu.
W pierwszym wierszu jedna liczba n określająca ilość liczb całkowitych (0 < n < 1 000 001).
Następnie n posortowanych niemalejąco liczb całkowitych, gdzie każda mieści się w przedziale [-230, 230].
W trzecim wierszu jedna liczba q określająca liczbę zapytań (0 < q < 300 001).
W ostatnim wierszu q liczb całkowitych należących do przedziału [-230, 230].
Dla każdego zapytania napis Tak, jeśli dana liczba powtórzyła się co najmniej trzy razy, napis Nie jeśli liczba powtórzyła się mniej niż trzy razy i przynajmniej raz lub napis brak, jeśli dana liczba nie występuje w ciągu.
Wejście: 10 1 2 2 2 3 3 4 4 4 5 3 1 2 3 Wyjście: Nie Tak Nie
Zadanie polega na zeskalowaniu napisu. Skalować będziemy tylko jego szerokość. Napis będzie niezmieniony, gdy poziom skalowania będzie równy 1. Gdy poziom będzie równy n, to między każdą literę wstawiamy |n| - 1 spacji. Gdy n jest liczbą ujemną, napis powinien być wyświetlony od tyłu. Dla n = 0 wypisujemy tylko ostatnią literę. Na wyjściu nie mogą się pojawić zbędne spacje i znaki końca linii.
W pierwszym wierszu napis złożony z wielkich liter języka łacińskiego (maksymalnie 100 znaków).
W drugim wierszu jedna liczba q określająca liczbę zeskalowań danego napisu (q < 100).
Następnie q wierszy, w każdym wierszu liczba n określająca poziom zeskalowania (|n| < 101)
Dla każdego zapytania w osobnym wierszu zeskalowany napis
Wejście: FRAKTAL 5 -2 -1 0 1 2 Wyjście: L A T K A R F LATKARF L FRAKTAL F R A K T A L
System U2 to system, w którym komputery przechowują liczby całkowite. Algorytm zamiany liczby dziesiętnej na U2 opisany jest w tym miejscu. Napisz program, który zamieni liczbę całkowitą na system U2 lub wypisze napis "niewykonalne", w sytuacji, gdy nie da się zapisać liczby na podanym polu.
W pierwszym wierszu jedna liczba t określająca ilość zestawów danych (0 < t < 106).
Każdy zestaw składa się z dwóch liczb całkoiwtych n i p (|n| ≤ 260, 0 < p < 101) określające liczbę, którą trzeba zapisać systemie U2 na polu p bitów.
Dla każdego zestawu jedna liczba zapisana w systemie U2 lub napis "niewykonalne", w sytuacji, gdy liczba nie zmieści się na polu p bitów.
Wejście: 2 100 8 -100 8 Wyjście: 01100100 10011100
Wesoła rodzinka Państwa Bajtockich wybrała się w góry. Właśnie wędrują sobie gęsiego po śniegu. Pierwszy idzie mały Bitek, następnie jego mama Bajbitka a na końcu ojciec Bajtjusz.
Zadanie: napisz program, który określi, ile razy na odcinku k metrów ślady wszystkich trzech osób pokryją się.
Zakładamy, że wszyscy ruszają z tego samego miejsca, pierwszy ślad jest tuż przed linią startu oraz wielkość śladu jest pomijalnie mała.
W pierwszym i jedynym wierszu cztery liczby całkowite a, b, c oraz s, gdzie a, b i c to długości kroków, jakie stawiają osoby z rodzinki (w centymetrach), następnie liczba całkowita s, określająca długość trasy (w metrach), wszystkie te liczby zawierają się w przedziale: [1..1010]. (dane są tak dobrane, że do obliczeń wystarczą typy 64 bitowe)
Jedna liczba określająca ile razy pokryją się ślady wszystkich osób w rodzinie.
Wejście: 30 40 50 2 Wyjście: 0
Wejście: 30 30 60 3 Wyjście: 5
Liczby pierwsze to takie liczby naturalne, które są większe od 1 i mają dokładnie dwa dzielniki (dzielą się tylko przez jeden i przez samą siebie). Pojęcie to nie jest trudne i uczy się o o tym już w szkole podstawowej, jednakże największe umysły matematyczne nie uporały sobie ze znalezieniem ogólnego wzoru na nie. Takie sławy jak Pierre de Fermat, Martin Mersenne, Leonhard Euler czy Johann Carl Friedrich Gauss zmagali się z tymi wspaniałymi liczbami tworząc często błędne Hipotezy. Na szczęście twoje zadanie nie będzie aż tak skomplikowane. Dziś zajmiemy się liczbami naturalnymi, które nie są pierwsze. Napisz program, który określi, jaki jest maksymalny podzbiór kolejnych liczb naturalnych należących do przedziału obustronnie domkniętego, które nie są pierwsze.
W pierwszym wierszu jedna liczba n określająca ilość zestawów danych (0 < n ≤105). Każdy zestaw składa się z dwóch liczb a, b reprezentujących przedział[a, b], gdzie 0 ≤ a ≤ b ≤ 4⋅106.
Dla każdego zestawu znajdź największy spójny podciąg kolejnych liczb naturalnych, które nie są pierwsze
Wejście: 3 1 10 10 10000 20 22 Wyjście: 3 35 3
Rozważmy zbiór punktów na płaszczyźnie kartezjańskiej, gdzie każdy punkt jest reprezentowany przez dwie liczby całkowite x i y oraz ich liczba nie przekracza 103. Napisz program, który stwierdzi, czy istnieje w danym zbiorze taka trójka punktów, które są współliniowe.
W pierwszym wierszu jedna liczba t określająca liczbę zestawów danych (t < 100).
Każdy zestaw składa się z jednej liczby n określającej liczbę punktów (2 < n < 1001). Każdy punkt zapisany jest w oddzienym wierszu za pomocą dwóch liczb całkowitych x i y (|x| < 109, |y| < 109).
Dla każdego zestawu napis Tak, jeśli istnieje szukana trójka oraz napis Nie w przeciwnym razie.
Wejście: 3 3 1 1 2 2 3 3 3 1 1 2 2 1 2 3 1 2 2 3 -1 0 Wyjście: Tak Nie Tak
Jasio jest już w czwartej klasie. Dziś poznaje cechy podzielności liczb naturalnych. Jako pracę domową, uczeń miał określić, czy dana liczba jest podzielna przez trzy. Profesor zapisał kilka przykładów na tablicy, ale niestety jego pismo ma wiele do życzenia, nie jest ono zbyt czytelne. Niektórych cyfr podanych liczb Jasio nie był wstanie prawidłowo odczytać. Postanowił więc, że w te miejsca dopasuje tak cyfry, żeby dana liczba była podzielna przez 3. Dodatkowo chce wypisać wszystkie możliwe kombinacje takich liczb. Niestety okazało się, że dla niektórych z nich jest to zbyt duża liczba możliwości. Zrezygnował więc z wypisania wszystkich liczb, a pozostał przy określeniu liczby kombinacji. A co Ty byś zrobił w takiej sytuacji? Ty napisałbyś program, który rozwiąże problem za Ciebie :).
Wejście składa się z pewnej liczby zestawów danych (nie więcej niż milion). Każdy zestaw składa się z jednej liczby, której nieczytelne cyfry zastąpiono znakiem (?). Liczba posiada maksymalnie dziesięć cyfr lub znaków (?). Popatrz na wyjaśnienie.
Dla każdego zestawu danych, liczba kombinacji jakich można uzyskać zamieniając znaki (?) na cyfry, aby otrzymać liczby podzielne przez trzy.
Wejście: 2?3 ?33 11?? Wyjście: 3 3 33 Wyjaśnienie Dla 2?3 uzyskujemy następujące liczby: 213, 243 oraz 273. Dla liczby ?33: 333, 633 oraz 933 (uwaga 033 nie traktujemy jako liczbę). Dla liczby 11?? mamy: 1101, 1104, ..., 1197.
Jasiu został uczniem pierwszej klasy szkoły podstawowej. Szkoła bardzo mu się podoba, bo jest dużo dzieci i sporo można się nauczyć. Z nauką jest jednak pewien problem, bo pani codziennie odpytuje z poprzednich zajęć, każdego dnia innego ucznia i nigdy nie wiadomo kto to będzie. Jasiu jest jednak bystry i już po tygodniu odgadł klucz, według którego odpytywani są uczniowie. Pani odpytuje według porządku wieku, starszy uczeń będzie pytany przed młodszym, a gdy co najmniej dwaj uczniowie urodzili się tego samego dnia miesiąca i roku, o porządku decyduje numer w dzienniku. Uczeń z przyporządkowanym niższym numerem będzie odpowiadał jako pierwszy. Teraz wystarczy zrobić listę porządkową kolejności odpytywań i każdy uczeń będzie wiedział, którego dnia będzie musiał odpowiadać na niekoniecznie łatwe pytania swojej pani.
Wejście
Pierwszy wiersz wejścia podaje liczbę przypadków testowych d (1 ≤ d ≤ 100). Dla każdego przypadku testowego, w pierwszym wierszu podana jest liczba całkowita n (1 ≤ n ≤ 104) oznaczająca liczbę uczniów. W kolejnych n wierszach opisane są dane ucznia potrzebne do ustalenia porządku: unikalny numer w dzienniku i data urodzenia w formacie RRRR-MM-DD. Między przypadkami testowymi występuje dodatkowy znak końca linii.
Wyjście
Dla każdego przypadku testowego w osobnym wierszu należy wypisać listę porządkową numerów, według kolejności odpytywań.
Przykład
Wejście
1
5
3 2007-12-15
1 2008-03-30
5 2007-05-02
2 2007-05-02
4 2008-11-17
Wyjście
2 5 3 1 4
Z podanego ciągu liczb wyznacz najdłuższy spójny podciąg o różnych wartościach.
Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 100). Każdy przypadek opisany jest w dwóch wierszach. W pierwszym podana jest liczba całkowita n (1 ≤ n ≤ 106) oznaczająca długość ciągu. W wierszu drugim danych jest n wyrazów ai ciągu (1 ≤ ai ≤ 1000).
Wyjście
Dla każdego przypadku testowego należy podać w pierwszym wierszu długość takiego podciągu, w wierszu drugim szukany podciąg. Jeśli istnieje więcej niż jeden podciąg o najdłuższej długości, należy wypisać ten, który wystąpi w ciągu jako pierwszy.
Przykład
Wejście
2
10
7 1 9 5 3 1 2 10 3 9
5
4 2 5 4 4
Wyjście
6
9 5 3 1 2 10
3
4 2 5
Jasiu uczęszcza na dodatkowe zajęcia z gimnastyki, gdzie trener dzieli uczniów na drużyny. Za każdym razem uczniowie w pewnym porządku zajmują punkty na okręgu. Odbywa się to w taki sposób, ze uczeń nr 1 zajmuje dowolny punkt na okręgu, uczeń nr 2 z punktu, w którym stoi pierwszy uczeń odlicza dwa punkty w kierunku zgodnym z ruchem wskazówek zegara i zajmuje ten punkt. Z tego punktu, kolejny uczeń nr 3 odlicza trzy punkty i zajmuje ten punkt, itd.. Proces ten powtarzany jest tak długo, aż wszyscy uczniowie zostaną przyporządkowani pewnym punktom. Niektóre z tych punktów będą miały przyporządkowanych więcej niż jednego ucznia, a niektóre nie będą miały w ogóle przyporządkowanych uczniów. Uczniowie przyporządkowani do jednego punktu tworzą drużynę, a pierwszy uczeń, który zajmie ten punkt zostaje kapitanem. Niektórzy uczniowie zanim zaczną odliczać po okręgu, chcieliby wiedzieć wcześniej z kim będą w drużynie, i co najważniejsze, kto będzie kapitanem drużyny. Twoim zadaniem jest wyjść naprzeciw oczekiwaniom uczniów i znając ich numer porządkowy odpowiedzieć na pytanie, kto będzie kapitanem drużyny.
Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 100). Każdy przypadek opisany jest w dwóch wierszach. W pierwszym wierszu znajdują się dwie liczby całkowite n i q (2 ≤ n, ≤ 1000, 1 ≤ q ≤ 1000), gdzie n oznacza liczbę punktów na okręgu, a q to liczba zapytań niektórych uczniów. W wierszu drugim danych jest q liczb ai (1 ≤ ai ≤ 105) oznaczających numery porządkowe uczniów, którzy chcą znać swojego kapitana, zanim zaczną swój marsz po okręgu.
Wyjście
Dla każdego zapytania ai należy podać numer porządkowy ucznia, który będzie kapitanem drużyny, do której należeć będzie uczeń z numerem ai. Na zapytania odpowiadamy w takiej kolejności, w jakiej zostały podane na wejściu.
Przykład
Wejście
1
14 8
4 14 15 3 5 14 11 12
Wyjście
4 6 8 3 1 6 4 8
Mały Jasio uczęszcza na zajęcia taneczne, gdzie wraz z innymi chłopcami i dziewczynkami ćwiczą różne układy taneczne. W tym tygodniu ćwiczą taniec węża, tzn. przytupują w rytm salsy trzymając się za ręce. Prowadząca zajęcia chciałaby sprawdzić swoich podopiecznych we wszystkich możliwych ustawieniach, ale nie wie jak to zrobić. Przyjmując, że chłopcy i dziewczynki są nierozróżnialni na poziomie płci, pomóż prowadzącej i wydrukuj dla niej wszystkie kombinacje ustawień chłopców i dziewczynek w rzędzie.
Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (d ≤ 100). Każdy przypadek opisany jest w osobnym wierszu, gdzie podane są dwie liczby całkowite a, b (1 ≤ a+b ≤ 20) oznaczające odpowiednio liczbę chłopców i liczbę dziewcząt w grupie.
Wyjście
Dla każdego przypadku testowego należy wypisać w osobnych wierszach wszystkie kombinacje ustawień chłopców i dziewcząt w porządku leksykograficznym, przypisując chłopcom literę a, a dziewczętom literę b. Między przypadkami testowymi można wypisać dodatkowy znak końca linii, ale nie jest on wymagany.
Przykład
Wejście
3
1 1
2 1
5 0
Wyjście
ab
ba
aab
aba
baa
aaaaa
Dla ilu całkowitych wartości k (0 ≤ k ≤ n), liczba nk (n nad k) jest podzielna przez 4?
Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (d ≤ 1000). Dla każdego przypadku testowego w osobnym wierszu podana jest jedna liczba naturalna n, (1 ≤ n ≤ 109)
Wyjście
Dla każdego przypadku testowego należy wypisać jedną liczbę będącą odpowiedzią na pytanie postawione w zadaniu.
Przykład
Wejście
2
6
10
Wyjście
1
3
Zadanie posiada 10 testów, każdy test za 10 punktów.
Test 1: (n < 64)
Test ≤ 5: (n < 105)
Test > 5: (105 ≤ n ≤ 109)
Zadanie zostanie zaakceptowane, jeśli uzyskasz co najmniej 50/100 punktów.