Problem: Ilya the Lion wants to help all his friends with passing exams. They need to solve the following problem to pass the IT exam.

You've got string s = s1s2... sn (n is the length of the string), consisting only of characters "." and "#" and m queries. Each query is described by a pair of integers li, ri (1 ≤ li < ri ≤ n). The answer to the query li, ri is the number of such integers i (li ≤ i < ri), that si = si + 1.

Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem.

Input

The first line contains string s of length n (2 ≤ n ≤ 105). It is guaranteed that the given string only consists of characters "." and "#".

The next line contains integer m (1 ≤ m ≤ 105) — the number of queries. Each of the next m lines contains the description of the corresponding query. The i-th line contains integers li, ri (1 ≤ li < ri ≤ n).

Output

Print m integers — the answers to the queries in the order in which they are given in the input.

Examples

Input

......
4
3 4
2 3
1 6
2 6


Output

1
1
5
4


Input

#..###
5
1 3
5 6
1 5
3 6
3 4


Output

1
1
2
2
0

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.lang.*;

public class codeforces {
   public static void main(String[] args) {
      InputStream inputStream = System.in;
      OutputStream outputStream = System.out;
      if (System.getProperty("ONLINE_JUDGE") == null) {
         long startTime = System.currentTimeMillis();
         try {
            sc = new InputReader(new FileInputStream("input.txt"));
            out = new PrintWriter(new FileOutputStream("output.txt"));
            pr = new PrintWriter(new FileOutputStream("error.txt"));
         } catch (Exception ignored) {
         }
         int t = 1;
         // t = sc.nextInt();
         while (t-- > 0) {
            solve();
         }
         long endTime = System.currentTimeMillis();
         System.out.println("Time: " + (endTime - startTime) + " ms");
         out.flush();
         pr.flush();

      } else {
         sc = new InputReader(inputStream);
         out = new PrintWriter(outputStream);
         pr = new PrintWriter(outputStream);
         int t = 1;
         // t = sc.nextInt();
         while (t-- > 0) {
            solve();
         }
         out.flush();
      }
   }

   public static void solve() {
      String str = sc.next();
      int m = sc.nextInt();
      int[] dp = new int[str.length()];
      for (int i = 0; i < str.length() - 1; i++) {
         if (str.charAt(i) == str.charAt(i + 1)) {
            if (i != 0)
               dp[i] = dp[i - 1] + 1;
            else
               dp[i] = 1;
         } else {
            if (i != 0)
               dp[i] = dp[i - 1];
            else
               dp[i] = 0;
         }
      }
      while (m-- > 0) {
         int l = sc.nextInt() - 1;
         int r = sc.nextInt() - 1;
         int ans = dp[r - 1];
         if (l > 0)
            ans -= dp[l - 1];
         out.println(ans);
      }
   }
   // Map Iterator:
   // for (Map.Entry<Integer, Integer> entry : map.entrySet()){}
   // System.out.println("Key => " + entry.getKey() + ", Value => " +
   // entry.getValue());}

   // Globals

   public static int inf = Integer.MAX_VALUE;
   public static int minf = Integer.MIN_VALUE;
   public static int mod = 1000000007;
   public static int ml = (int) 1e9;
   public static InputReader sc;
   public static PrintWriter out;
   public static PrintWriter pr;

   // Pair

   static class Pair {
      int first, second;

      Pair(int x, int y) {
         this.first = x;
         this.second = y;
      }
   }

   // FastReader Class

   static class InputReader {
      public BufferedReader reader;
      public StringTokenizer tokenizer;

      public InputReader(InputStream stream) {
         reader = new BufferedReader(new InputStreamReader(stream), 32768);
         tokenizer = null;
      }

      public String next() {
         while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
               tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
               throw new RuntimeException(e);
            }
         }
         return tokenizer.nextToken();
      }

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

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

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

   // Req Functions
   public static void fill2d(int[][] dp, int x) {
      for (int i = 0; i < dp.length; ++i) {
         for (int j = 0; j < dp[0].length; ++j) {
            dp[i][j] = x;
         }
      }
   }

   public static int[] fill(int n, int x) {
      int[] arr = new int[n];
      Arrays.fill(arr, x);
      return arr;
   }

   public static int gcd(int a, int b) {
      if (a == 0)
         return b;
      return gcd(b % a, a);
   }

   public static int lcm(int a, int b) {
      return (a / gcd(a, b)) * b;
   }

   public static long gcd(long a, long b) {
      if (a == 0)
         return b;
      return gcd(b % a, a);
   }

   public static long lcm(long a, long b) {
      return (a / gcd(a, b)) * b;
   }

   public static int countDigits(int l) {
      if (l >= 1000000000)
         return 10;
      if (l >= 100000000)
         return 9;
      if (l >= 10000000)
         return 8;
      if (l >= 1000000)
         return 7;
      if (l >= 100000)
         return 6;
      if (l >= 10000)
         return 5;
      if (l >= 1000)
         return 4;
      if (l >= 100)
         return 3;
      if (l >= 10)
         return 2;
      return 1;
   }

   public static int countDigits(long l) {
      if (l >= 1000000000000000000L)
         return 19;
      if (l >= 100000000000000000L)
         return 18;
      if (l >= 10000000000000000L)
         return 17;
      if (l >= 1000000000000000L)
         return 16;
      if (l >= 100000000000000L)
         return 15;
      if (l >= 10000000000000L)
         return 14;
      if (l >= 1000000000000L)
         return 13;
      if (l >= 100000000000L)
         return 12;
      if (l >= 10000000000L)
         return 11;
      if (l >= 1000000000L)
         return 10;
      if (l >= 100000000L)
         return 9;
      if (l >= 10000000L)
         return 8;
      if (l >= 1000000L)
         return 7;
      if (l >= 100000L)
         return 6;
      if (l >= 10000L)
         return 5;
      if (l >= 1000L)
         return 4;
      if (l >= 100L)
         return 3;
      if (l >= 10L)
         return 2;
      return 1;
   }

   public static long nCr(int n, int k) {
      long ans = 1L;
      k = k > n - k ? n - k : k;
      int j = 1;
      for (; j <= k; j++, n--) {
         if (n % j == 0) {
            ans *= n / j;
         } else if (ans % j == 0) {
            ans = ans / j * n;
         } else {
            ans = (ans * n) / j;
         }
      }
      return ans;
   }

   public static String reverseString(String input) {
      StringBuilder str = new StringBuilder("");

      for (int i = input.length() - 1; i >= 0; i--) {
         str.append(input.charAt(i));
      }
      return str.toString();
   }

   public static int maxOf3(int x, int y, int z) {
      return Math.max(x, Math.max(y, z));
   }

   public static int minof3(int x, int y, int z) {
      return Math.min(x, Math.min(y, z));
   }

   public static long maxOf3(long x, long y, long z) {
      return Math.max(x, Math.max(y, z));
   }

   public static long minof3(long x, long y, long z) {
      return Math.min(x, Math.min(y, z));
   }

   public static void arrInput(int[] arr, int n) {
      for (int i = 0; i < n; i++)
         arr[i] = sc.nextInt();
   }

   public static void arrInput(long[] arr, int n) {
      for (int i = 0; i < n; i++)
         arr[i] = sc.nextLong();
   }

   public static void arrInput(Pair[] pair, int n) {
      for (int i = 0; i < n; i++)
         pair[i] = new Pair(sc.nextInt(), sc.nextInt());
   }

   public static int maxarrInput(int[] arr, int n) {
      int max = 0;
      for (int i = 0; i < n; i++) {
         arr[i] = sc.nextInt();
         max = Math.max(max, arr[i]);
      }
      return max;

   }

   public static long maxarrInput(long[] arr, int n) {
      long max = 0;
      for (int i = 0; i < n; i++) {
         arr[i] = sc.nextLong();
         max = Math.max(max, arr[i]);
      }
      return max;
   }

   public static int minarrInput(int[] arr, int n) {
      int min = Integer.MAX_VALUE;
      for (int i = 0; i < n; i++) {
         arr[i] = sc.nextInt();
         min = Math.max(min, arr[i]);
      }
      return min;
   }

   public static long minarrInput(long[] arr, int n) {
      long min = 0;
      for (int i = 0; i < n; i++) {
         arr[i] = sc.nextLong();
         min = Math.max(min, arr[i]);
      }
      return min;
   }

   public static long sumofarr(int[] arr) {
      long sum = 0;
      for (int i : arr)
         sum += i;
      return sum;
   }

   public static long sumofarr(long[] arr) {
      long sum = 0;
      for (long i : arr)
         sum += i;
      return sum;
   }

   public static int lowerBound(int[] arr, int x) {
      int l = -1, r = arr.length;
      while (l + 1 < r) {
         int m = (l + r) >>> 1;
         if (arr[m] >= x)
            r = m;
         else
            l = m;
      }
      return r;
   }

   public static int upperBound(int[] arr, int x) {
      int l = -1, r = arr.length;
      while (l + 1 < r) {
         int m = (l + r) >>> 1;
         if (arr[m] <= x)
            l = m;
         else
            r = m;
      }
      return l + 1;
   }

   public static long maxofarr(long[] arr) {
      long max = 0;
      for (long i : arr)
         max = Math.max(i, max);
      return max;
   }

   public static long minofarr(long[] arr) {
      long min = Integer.MAX_VALUE;
      for (long i : arr)
         min = Math.min(min, i);
      return min;
   }

   public static int maxofarr(int[] arr) {
      int max = 0;
      for (int i : arr)
         max = Math.max(i, max);
      return max;
   }

   public static int minofarr(int[] arr) {
      int min = Integer.MAX_VALUE;
      for (int i : arr)
         min = Math.min(min, i);
      return min;
   }

   // debug

   public static boolean sysFlag = System.getProperty("ONLINE_JUDGE") == null;

   public static void debug(int[][] dp) {
      if (sysFlag) {
         for (int i = 0; i < dp.length; ++i) {
            pr.print(i + "--> ");
            for (int j = 0; j < dp[0].length; ++j) {
               pr.print(dp[i][j] + " ");
            }
            pr.println("");
         }
      }
   }

   public static void debug(long[][] dp) {
      if (sysFlag) {
         for (int i = 0; i < dp.length; ++i) {
            pr.print(i + "--> ");
            for (int j = 0; j < dp[0].length; ++j) {
               pr.print(dp[i][j] + " ");
            }
            pr.println("");
         }
      }
   }

   public static void debug(int x) {
      if (sysFlag)
         pr.println("Int-Ele: " + x);
   }

   public static void debug(String x) {
      if (sysFlag)
         pr.println("String: " + x);
   }

   public static void debug(char x) {
      if (sysFlag)
         pr.println("Char: " + x);
   }

   public static void debug(long x) {
      if (sysFlag)
         pr.println("Long-Ele: " + x);
   }

   public static void debug(int[] arr) {
      if (sysFlag) {
         for (int i = 0; i < arr.length; ++i) {
            pr.println(i + " -> " + arr[i]);
         }
      }
   }

   public static void debug(int[] arr, int n) {
      if (sysFlag) {
         for (int i = 0; i < n; ++i) {
            pr.println(i + " -> " + arr[i]);
         }
      }
   }

   public static void debug(long[] arr) {
      if (sysFlag) {
         for (int i = 0; i < arr.length; ++i) {
            pr.println(i + " -> " + arr[i]);
         }
      }
   }

   public static void debug(ArrayList<Integer> list) {
      if (sysFlag) {
         for (int i = 0; i < list.size(); ++i) {
            pr.println(i + " -> " + list.get(i));
         }
      }
   }

   public static void Ldebug(ArrayList<Long> list) {
      if (sysFlag) {
         for (int i = 0; i < list.size(); ++i) {
            pr.println(i + " -> " + list.get(i));
         }
      }
   }

   public static void debugmapII(HashMap<Integer, Integer> map) {
      if (sysFlag) {
         for (Map.Entry<Integer, Integer> entry : map.entrySet())
            pr.println("Key => " + entry.getKey() + ", Value => " + entry.getValue());
      }
   }

   public static void debugmapLI(HashMap<Long, Integer> map) {
      if (sysFlag) {
         for (Map.Entry<Long, Integer> entry : map.entrySet())
            pr.println("Key => " + entry.getKey() + ", Value => " + entry.getValue());
      }
   }

   public static void debugmapLL(HashMap<Long, Long> map) {
      if (sysFlag) {
         for (Map.Entry<Long, Long> entry : map.entrySet())
            pr.println("Key => " + entry.getKey() + ", Value => " + entry.getValue());
      }
   }

   public static void debugmapIL(HashMap<Integer, Long> map) {
      if (sysFlag) {
         for (Map.Entry<Integer, Long> entry : map.entrySet())
            pr.println("Key => " + entry.getKey() + ", Value => " + entry.getValue());
      }
   }

   public static void debugmapSL(HashMap<String, Long> map) {
      if (sysFlag) {
         for (Map.Entry<String, Long> entry : map.entrySet())
            pr.println("Key => " + entry.getKey() + ", Value => " + entry.getValue());
      }
   }

   public static void debugmapCL(HashMap<Character, Long> map) {
      if (sysFlag) {
         for (Map.Entry<Character, Long> entry : map.entrySet())
            pr.println("Key => " + entry.getKey() + ", Value => " + entry.getValue());
      }
   }

   public static void debugmapSI(HashMap<String, Integer> map) {
      if (sysFlag) {
         for (Map.Entry<String, Integer> entry : map.entrySet())
            pr.println("Key => " + entry.getKey() + ", Value => " + entry.getValue());
      }
   }

   public static void debugmapCI(HashMap<Character, Integer> map) {
      if (sysFlag) {
         for (Map.Entry<Character, Integer> entry : map.entrySet())
            pr.println("Key => " + entry.getKey() + ", Value => " + entry.getValue());
      }
   }

}