## PROG0328 - Thue-Morse sequence

The Thue-Morse sequence is a binary sequence - an infinite sequence of zeroes and ones. The sequence is obtained by starting from the string 0, and constantly expanding it with the Boolean complement of the obtained string so far. The Boolean complement of a binary string is obtained by replacing all zeroes with ones and all ones with zeroes. This procedure therefore starts with the string 0, and successively delivers the strings 01, 0110, 01101001, 0110100110010110, and so on.

Graphic demonstration of the repeated binary expansion of the Thue-Morse sequence.

The Thue-Morse sequence has many stunning features. For example, the binary sequence is cube-free: it does not contain 000,111,010101, or more generally bbb in which b represents a random binary string. The sequence is also self-similar: if you remove every other bit from the series, you again obtain a Thue-Morse sequence. This sequence has many applications in mathematics, and is also used in chess, graphic design, weaving patterns and composing music.

### Input

The first line of the input contains an integer $t \in \mathbb{N}$ indicating the number of test cases. This is followed by $t$ lines that each describe a test case. Each of these lines consists of two integers $s$ and $l$, separated by a space.

### Output

For each test case, print the substring of the Thue-Morse sequence, starting at position $s$ and is $l$ binary digits long. We index the positions of the binary digits from zero.

### Example

Input:

57645 378956 284724 268829 176051 12


Output:

001100101100110100101101001100101100101101001011001101001011010010110011010011001011001101000110010110011010010011001011


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.

Grafische demonstratie van de herhaalde binaire complementsuitbreiding van de Thue-Morse reeks.

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:

57645 378956 284724 268829 176051 12


Uitvoer:

001100101100110100101101001100101100101101001011001101001011010010110011010011001011001101000110010110011010010011001011


 Added by: Peter Dawyndt Date: 2013-02-16 Time limit: 10s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: PY_NBC Resource: None

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.