There is a bulb, which can have two states, ON or OFF. You are given the initial state of the bulb s and a binary string d which has either 0's or 1's. A single flip is defined as changing one single bit from 0 to 1 or 1 to 0. You are given q queries, each having two integers l and r. They denote two positions in the binary string. The sequence of bits from l to r, denotes a decimal integer p. Find the state of the bulb after performing p flips.

Note that the state of the bulb is reverted back to its initial state after each query.

Jeel being a friend of yours and respected member of international coding community asks you to solve this problem for him.

Note: Use Fast I/O.

Input Format

First line contains number of test cases T.

Each test case has below input format:

First line contains s, initial state of bulb.

Second line has binary string d.

Third line has an integer q, number of queries.

Next q lines contain two integers l and r.

Output Format

For T test cases:

Output q lines, each having final state of bulb.

Constraints

s ∈ {ON,OFF}

1 <= T <= 10

1 <= length(d) <= 10⁵

1 <= l <= r <= length(d)

1 <= q <= 10⁵