De Thue-Morse reeks is een binaire reeks — een oneindige reeks van nullen en eentjes. De reeks wordt bekomen door te vertrekken van de string 0, en die steeds uit te breiden met het Booleaanse complement van de string die men tot dusver heeft bekomen. Het Booleaanse complement van een binaire string bekomt men door alle nullen te vervangen door eentjes en alle eentjes door nullen. Deze procedure start dus bij de string 0, en levert achtereenvolgens de strings 01, 0110, 01101001, 0110100110010110, enzoverder op.

De Thue-Morse reeks heeft heel wat verbluffende eigenschappen. Zo is het bijvoorbeeld een binaire reeks die kubus-vrij is: ze bevat geen 000, 111, 010101 of meer algemeen bbb waarbij b zelf een willekeurige binaire string voorstelt. De reeks is ook zelf-gelijkend: als je om het andere bit verwijdert uit de reeks, dan bekom je opnieuw een Thue-Morse reeks. Deze reeks heeft heel wat toepassingen in de wiskunde, en wordt ook gebruikt bij schaken, grafisch ontwerpen, weefpatronen¹ en het componeren van muziek.

Invoer

De eerste regel van de invoer bevat een getal $$t \in \mathbb{N}$$ dat het aantal testgevallen aangeeft. Daarna volgen $$t$$ regels die elk een testgeval omschrijven. Elk van deze regels bestaan uit twee natuurlijke getallen $$s$$ en $$l$$ die door een spatie van elkaar gescheiden worden.

Uitvoer

Schrijf voor elk testgeval de substring van de Thue-Morse reeks uit die start op positie $$s$$ en $$l$$ binaire cijfers lang is. We indexeren hierbij de posities van de binaire cijfers vanaf nul.

Voorbeeld

Invoer:

5
7645 37
8956 28
4724 26
8829 17
6051 12

Uitvoer:

0011001011001101001011010011001011001
0110100101100110100101101001
01100110100110010110011010
00110010110011010
010011001011