559aead08264d5795d3909718cdd05abd49572e84fe55590eef31a88a08fdffd ~(2^9)~

Trong một chuyến đi khám phá vườn hoa khổng lồ và đáng yêu gần nhà Peace và xa nhà Matcha Latte, Matcha Latte đã thu thập được một chuỗi ký tự ~s~ dài ~n~ (chỉ gồm các chữ cái từ a đến z) mô tả các loại hoa, lá, và cây cối đặc trưng của khu vườn. Chuỗi này là bản đồ chi tiết của cả khu vườn.

Peace, với trí tò mò của mình, đưa ra ~q~ câu đố. Mỗi câu đố gồm 4 số ~l, r, u, v~ ~(1 \leq l \leq r \leq n, 1 \leq u \leq v \leq n,~ luôn có ~r - l = v - u)~, đại diện cho việc chọn hai khu vực nhỏ trong vườn:

• Khu vực ~A~ được mô tả bởi chuỗi ~a = s[l..r]~.
• Khu vực ~B~ được mô tả bởi chuỗi ~b = s[u..v]~.

Nhiệm vụ của bạn là giúp Matcha Latte giải các câu đố này: Đối với mỗi câu đố, hãy đếm số lượng vị trí ~i~ (ở khu vực ~A~) sao cho ký tự hoa lá ở vị trí ~i~ trong chuỗi ~a~ giống hệt ký tự hoa lá ở vị trí tương ứng trong trong chuỗi ~b~ (ở khu vực ~B~).

Vì đây là vườn hoa gần nhà Peace, rất ít hoa nên theo lí thuyết, ít hoa thì số lượng câu hỏi không được phong phú như vườn hoa gần nhà Matcha Latte nên giới hạn bài này thuộc loại dễ: ~1 \leq n \leq 1000, 1 \leq q \leq 100~.

Input

• Dòng thứ nhất gồm một xẫu kí tự ~s~.
• Dòng thứ hai là một số nguyên dương ~q~.
• Trong ~q~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên dương ~l, r, u, v~.

Output

• Gồm ~q~ dòng, mỗi dòng in ra một số nguyên tương ứng với đáp án của mỗi câu đố.

Example input 1

abacaba
3
1 3 5 7
2 4 4 6
1 1 7 7

Example output 1

3
1
1

Note 1

• Câu đố ~1~: ~l = 1, r = 3, u = 5, v = 7~.

  • Khu vực A: ~s[0..2]~ ~=~ aba
  • Khu vực B: ~s[4..6]~ ~=~ aba
  • So sánh: a bằng a, b bằng b, a bằng a ~\rightarrow~ có ~3~ vị trí giống nhau.

• Câu đố ~2~: ~l = 2, r = 4, u = 4, v = 6~.

  • Khu vực A: ~s[1..3]~ ~=~ bac
  • Khu vực B: ~s[3..5]~ ~=~ cab
  • So sánh: b khác c, a bằng a, c khác b ~\rightarrow~ có ~1~ vị trí giống nhau.

• Câu đố ~3~: ~l = 1, r = 1, u = 7, v = 7~.

  • Khu vực A: ~s[0..0]~ ~=~ a
  • Khu vực B: ~s[6..6]~ ~=~ a
  • So sánh: a bằng a ~\rightarrow~ có ~1~ vị trí giống nhau.