This is the easy version of the problem. The difference between the versions is that the easy version does not require you to output the numbers of the rods to be removed. You can make hacks only if all versions of the problem are solved.

Stitch likes experimenting with different machines with his friend Sparky. Today they built another machine.

The main element of this machine are n rods arranged along one straight line and numbered from 1 to n inclusive. Each of these rods must carry an electric charge quantitatively equal to either 1 or -1 (otherwise the machine will not work). Another condition for this machine to work is that the sign-variable sum of the charge on all rods must be zero.

More formally, the rods can be represented as an array of n numbers characterizing the charge: either 1 or -1. Then the condition must hold: a_1 - a_2 + a_3 - a_4 + … = 0, or ∑_{i=1}^n (-1)^{i-1} ⋅ a_i = 0.

Sparky charged all n rods with an electric current, but unfortunately it happened that the rods were not charged correctly (the sign-variable sum of the charge is not zero). The friends decided to leave only some of the rods in the machine. Sparky has q questions. In the ith question Sparky asks: if the machine consisted only of rods with numbers l_i to r_i inclusive, what minimal number of rods could be removed from the machine so that the sign-variable sum of charges on the remaining ones would be zero? Perhaps the friends got something wrong, and the sign-variable sum is already zero. In that case, you don't have to remove the rods at all.

If the number of rods is zero, we will assume that the sign-variable sum of charges is zero, that is, we can always remove all rods.

Help your friends and answer all of Sparky's questions!

Input

Each test contains multiple test cases.

The first line contains one positive integer t (1 ≤ t ≤ 10^3), denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains two positive integers n and q (1 ≤ n, q ≤ 3 ⋅ 10^5) — the number of rods and the number of questions.

The second line of each test case contains a non-empty string s of length n, where the charge of the i-th rod is 1 if s_i is the "+" symbol, or -1 if s_i is the "-" symbol.

Each next line from the next q lines contains two positive integers l_i ans r_i (1 ≤ l_i ≤ r_i ≤ n) — numbers, describing Sparky's questions.

It is guaranteed that the sum of n over all test cases does not exceed 3 ⋅ 10^5, and the sum of q over all test cases does not exceed 3 ⋅ 10^5.

Output

For each test case, print a single integer — the minimal number of rods that can be removed.

Example

Input


3
14 1
+--++---++-++-
1 14
14 3
+--++---+++---
1 14
6 12
3 10
4 10
+-+-
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4


Output


2
2
1
0
1
2
1
2
1
2
1
1
2
1

Note

In the first test case for the first query you can remove the rods numbered 5 and 8, then the following set of rods will remain: +--+--++-++-. It is easy to see that here the sign-variable sum is zero.

In the second test case:

  * For the first query, we can remove the rods numbered 1 and 11, then the following set of rods will remain: --++---++---. It is easy to see that here the sign-variable sum is zero. 
  * For the second query we can remove the rod numbered 9, then the following set of rods will remain: ---++-. It is easy to see that here the variable sum is zero. 
  * For the third query we can not remove the rods at all. 
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class CodeForces {

    /**
     * Это простая версия задачи. Различия между версиями заключаются в том, что в простой версии не требуется выводить
     * номера удаляемых стержней. Вы можете делать взломы, только если обе версии задачи сданы.
     * <p>
     * Стич любит экспериментировать с различными механизмами вместе со своим другом Спарки.
     * Сегодня они построили очередную машину.
     * <p>
     * Главным элементом этой машины являются n стержней, расположен9ных вдоль одной прямой и пронумерованных
     * от 1 до n включительно. На каждом из этих стержней должен находиться электрический заряд, количественно
     * равный либо 1, либо −1 (иначе машина не будет работать). Другим условием работы этой машины является то,
     * что знакопеременная сумма заряда по всем стержням должна равняться нулю.
     * <p>
     * Более формально, стержни можно представить как массив из n чисел, характеризующих заряд: либо 1, либо −1.
     * Тогда должно выполняться условие: a1−a2+a3−a4+…=0, или, выражаясь проще, ∑i=1n(−1)i−1⋅ai=0.
     * <p>
     * Спарки зарядил все n стержней электрическим током, но оказалось,
     * что стержни заряжены неправильно (знакопеременная сумма заряда не равна нулю).
     * Друзья решили оставить в машине только часть стержней. У Спарки есть q вопросов. В i-м вопросе Спарки интересуется:
     * если бы машина состояла только из стержней с номерами с li по ri включительно,
     * какое минимальное количество стержней можно было бы удалить из машины так, чтобы знакопеременная
     * сумма зарядов на оставшихся была равна нулю? Возможно, друзья что-то напутали, и знакопеременная
     * сумма уже равна нулю. В таком случае, можно не удалять стержни вовсе.
     * <p>
     * Если количество стержней равно нулю, будем считать, что знакопеременная сумма зарядов равна нулю,
     * то есть всегда можно удалить все стержни.
     * <p>
     * Помогите друзьям и ответьте на все вопросы Спарки!
     * <p>
     * Входные данные
     * Каждый тест содержит несколько наборов входных данных.
     * <p>
     * В первой строке находится одно целое положительное число t (1≤t≤103) — количество наборов входных данных.
     * Описание наборов входных данных приведено ниже.
     * <p>
     * В первой строке каждого набора входных данных находятся два целых числа n и q (1≤n,q≤3⋅105) — количество
     * стержней и количество вопросов соответственно.
     * <p>
     * Во второй строке находятся строка s длины n, где заряд i-го стержня равен 1, если si это символ «+»,
     * или −1, если si это символ «-».
     * <p>
     * Каждая из следующих q строк содержит два целых положительных числа li и ri (1≤li≤ri≤n) — числа,
     * описывающие вопросы Спарки.
     * <p>
     * Гарантируется, что сумма n по всем наборам входных данных не превосходит 3⋅105, а также сумма q по всем
     * тестовым случаям не превосходит 3⋅105.
     * <p>
     * Выходные данные
     * Для каждого набора входных данных выведите в отдельной строке одно целое число — минимальное
     * количество стержней, которое можно удалить.
     * <p>
     * +--++---++-++-
     * В первом наборе входных данных для первого запроса можно удалить стержни под номерами 5 и 8,
     * тогда останется следующий набор стержней: +--+--++-++-. Нетрудно видеть, что здесь знакопеременная сумм равна нулю.
     * <p>
     * В втором наборе входных данных:
     * <p>
     * Для первого запроса можно удалить стержни под номерами 1 и 11,
     * тогда останется следующий набор стержней: +--+--++-++-. Нетрудно видеть, что здесь знакопеременная сумма равна нулю.
     * Для второго запроса можно удалить стержень под номером 9,
     * тогда останется следующий набор стержней: ---++-. Нетрудно видеть, что здесь знакопеременная сумма равна нулю.
     * Для третьего запроса можно не удалять стержни вовсе.
     */
//eoeoeoeo
//-++---++

    public static class ContestSolution extends Solution {

        boolean[] remove(boolean[] a, int i) {
            int n = a.length;
            boolean[] b = new boolean[n - 1];
            System.arraycopy(a, 0, b, 0, i);
            System.arraycopy(a, i + 1, b, i + 1 - 1, n - (i + 1));
            return b;
        }

        int calc(boolean[] a) {
            int n = a.length;
            int ans = 0;
            for (int i = 0; i < n - 1; i++) {
                ans += (i % 2 == 0 == a[i]) ? 1 : -1;
            }
            return ans;
        }

        void solve() {
            int n = in.nextInt();
            int q = in.nextInt();
            String s = in.nextLine();
            boolean[] a = new boolean[n];
            for (int i = 0; i < n; i++) {
                a[i] = s.charAt(i) == '+';
            }
            int[] even = new int[n];
            int[] odd = new int[n];

            even[0] = a[0] ? 1 : 0;
            for (int i = 1; i < n; i++) {
                even[i] += even[i - 1];
                odd[i] += odd[i - 1];
                if (i % 2 == 0) {
                    even[i] += a[i] ? 1 : 0;
                } else {
                    odd[i] += a[i] ? 1 : 0;
                }
            }

            for (int i = 0; i < q; i++) {
                int l = in.nextInt() - 1;
                int r = in.nextInt() - 1;
                if ((l - r) % 2 == 0) {
                    out.println(1);
                } else {
                    int e = even[r] - (l > 0 ? even[l - 1] : 0);
                    int o = odd[r] - (l > 0 ? odd[l - 1] : 0);
                    if (e == o) {
                        out.println(0);
                    } else {
                        out.println(2);
                    }
                }

            }
        }
    }

    /**
     * add `-Xss256m` to increase stack size
     */
    public static void main(String[] args) {
        boolean local = args.length > 0;
//        boolean local = false;
        String input = local ? "codeforces/input.txt" : null;

        Solution solution = new ContestSolution();
        solution.in = new MyScanner(input);
        solution.out = MyWriter.of(null);
        solution.bm = new Benchmark();
        solution.al = new Algorithm();
        solution.run();
        solution.out.close();
    }

    public static class Solution {
        public MyScanner in;
        public MyWriter out;
        public Benchmark bm;
        public Algorithm al;

        void init() {
        }

        void solve() {
        }

        boolean isMultiTest() {
            return true;
        }

        void run() {
            init();
            if (isMultiTest()) {
                int t = in.nextInt();
                for (int i = 0; i < t; i++) {
                    solve();
                }
            } else {
                solve();
            }
        }

    }

    public static class Algorithm {
        public void sort(int[] arr) {
            List<Integer> tmp = Arrays.stream(arr).boxed().sorted().collect(Collectors.toList());
            for (int i = 0; i < arr.length; i++) {
                arr[i] = tmp.get(i);
            }
        }

        public void sortRev(int[] arr) {
            List<Integer> tmp = Arrays.stream(arr).boxed().sorted(Comparator.comparing((Integer x) -> x).reversed())
                    .collect(Collectors.toList());
            for (int i = 0; i < arr.length; i++) {
                arr[i] = tmp.get(i);
            }
        }
    }

    public static class ModInt {
        static int MOD = 1000000007;

        public static final ModInt ZERO = new ModInt(0);
        public static final ModInt ONE = new ModInt(1);

        private static final Map<ModInt, ModInt> inverseCache = new HashMap<>();

        private final int value;

        public ModInt(int value) {
            if (value < 0) {
                throw new IllegalArgumentException();
            }
            this.value = value;
        }

        public ModInt add(ModInt other) {
            return new ModInt((int) (((long) this.value + other.value) % MOD));
        }

        public ModInt subtract(ModInt other) {
            return new ModInt((int) (((long) this.value - other.value + MOD) % MOD));
        }

        public ModInt multiply(ModInt other) {
            return new ModInt((int) (((long) this.value * other.value) % MOD));
        }

        public ModInt pow(int degree) {
            if (degree == 0) {
                return ModInt.ONE;
            }
            if (degree % 2 == 1) {
                return this.multiply(pow(degree - 1));
            }
            ModInt tmp = this.pow(degree / 2);
            return tmp.multiply(tmp);
        }

        public ModInt inverse() {
            ModInt tmp = inverseCache.get(this);
            if (tmp == null) {
                tmp = this.pow(MOD - 2);
                inverseCache.put(this, tmp);
            }
            return tmp;
        }

        public ModInt divide(ModInt other) {
            return this.multiply(other.inverse());
        }
    }

    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner(String fileName) {
            if (fileName != null) {
                try {
                    br = new BufferedReader(new FileReader(fileName));
                } catch (FileNotFoundException e) {
                    throw new RuntimeException(e);
                }
            } else {
                br = new BufferedReader(new InputStreamReader(System.in));
            }
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextInts(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

        boolean[] nextLineBools() {
            String line = nextLine();
            int n = line.length();
            boolean[] booleans = new boolean[n];
            for (int i = 0; i < n; i++) {
                booleans[i] = line.charAt(i) == '1';
            }
            return booleans;
        }

        char[] nextLineChars() {
            String line = nextLine();
            int n = line.length();
            char[] chars = new char[n];
            for (int i = 0; i < n; i++) {
                chars[i] = line.charAt(i);
            }
            return chars;
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        public long[] nextLongs(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            try {
                String line = br.readLine();
                if (line == null) {
                    throw new RuntimeException("empty line");
                }
                st = null;
                return line;
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
    }

    public static class MyWriter extends PrintWriter {

        public static MyWriter of(String fileName) {
            if (fileName != null) {
                try {
                    return new MyWriter(new FileWriter(fileName));
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            } else {
                return new MyWriter(new BufferedOutputStream(System.out));
            }
        }

        public MyWriter(FileWriter fileWriter) {
            super(fileWriter);
        }

        public MyWriter(OutputStream out) {
            super(out);
        }

        void println(int[] arr) {
            String line = Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(" "));
            println(line);
        }

    }

    public static class Benchmark {
        long time;

        public void start() {
            time = System.currentTimeMillis();
        }

        public long calc() {
            long curTime = System.currentTimeMillis();
            long tmp = curTime - time;
            time = curTime;
            return tmp;
        }

    }
}
