A conference of British scientists in the city of Bash ended with a sensation. Professor D. Cheatillo presented a talk that changed the modern idea of the world.

It was assumed earlier that DNA molecules of humans and animals consisted of four nucleotides only, which were denoted by the symbols “A”, “C”, “G”, and “T”. However, Professor Cheatillo proved that for each nucleotide there was the matching antinucleotide, which could also be present in a DNA molecule. Professor denoted the antinucleotides by the symbols “a”, “c”, “g”, and “t”, where “a” was the antinucleotide for “A”, “c” was the antinucleotide for “C”, and so on.

Moreover, the investigation carried out by Cheatillo showed that human DNA strands had special structure. Professor believes that each human DNA strand is either an empty string, or the concatenation of two human strands (i.e. a human strand followed by a human strand), or a human strand preceded by some nucleotide and followed by the matching antinucleotide. For example, the strands “CcAaGg” and “ACca” are human and the strands “cC” and “GTgt” are not.

Professor Cheatillo conjectures that the degree of the affinity between a human and an animal can be established by checking whether some substrings of a DNA strand of this animal are human. In order to develop an efficient method of performing such checks, British scientists invited the best programmers, which means you.

The first line contains a DNA strand of some animal. The line consists of the symbols “A”, “C”, “G”, “T”, “a”, “c”, “g”, “t” and has length L (1 ≤ L ≤ 100000). The second line contains the number q of substrings of this line that must be checked (1 ≤ q ≤ 50000). The i-th of the following q lines contains space-separated integers l_i and r_i, which are the numbers of the first and the last symbols of the substring that must be checked (1 ≤ l_i ≤ r_i ≤ L).

Output a string of length q consisting of symbols “0” and “1”. The i-th symbol must be “1” if the substring starting at position l_i and ending at position r_i is human. Otherwise, this symbol must be “0”.