Alice and Bob always had hard time choosing restaurant for the dinner. Previously they performed Eenie Meenie Miney Mo game, but eventually as their restaurant list grew, they had to create a new game. This new game starts as they write restaurant names on N cards and align the cards in one line. Before the game begins, they both choose starting card and starting direction they are going to. They take turns in order one after another. After each turn, they move one card in their current direction. If they reach the end or beginning of the line of cards they change direction. Once they meet in a card, the card is marked for removal and is removed the first moment they both leave the card.

<image> Example of how card is removed

They repeat this process until there is only one restaurant card left. Since there are a lot of restaurant cards, they are bored to simulate this process over and over and need your help to determine the last card that remains. Can you help them? 

Input

The first line of the input is one integer T (1 ≤ T ≤ 10^{4}) representing number of test cases. Each test case contains 3 lines: The first line contains an integer N representing initial number of cards. Next line contains two integer values A,B (0 ≤ A, B < N, 2 ≤ N ≤ 10^{18}) representing starting 0-based index of the card in the array. Last line contains two strings D_A, D_B ∈ {"left", "right"} representing starting direction of their movement.

Output

The output contains T integer number – the 0-based index of the last card that remains for every test case in order.

Example

Input


1
4
0 1
left right


Output


0

Note

Note that since Alice is starting at the beginning of the line even though her initial direction is left, on her next move she will go right.
10
429
41 20
left left
977
606 92
left left
874
742 866
right right
774
61 573
right right
315
160 287
right left
985
871 814
left right
73
0 45
right left
880
358 535
right left
842
457 592
right left
599
509 542
right left

428
0
873
773
0
984
0
0
0
0

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
void write(long long x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
long long n, A, B, x, y;
long long ans;
string a, b;
bool flag = 0;
void DOIT() {
  n = read();
  A = read();
  B = read();
  A++;
  B++;
  x = 0;
  y = 0;
  cin >> a >> b;
  if (A > B) {
    if (a == "left")
      A--;
    else
      A++;
    if (A == 0) A = 2;
    if (A == n + 1) A = n - 1;
    swap(A, B);
    swap(a, b);
  }
  if (A == 1 && B == 1) {
    if (1)
      cout << n - 1 << "\n";
    else
      cout << 0 << "\n";
    return;
  }
  if (A == 1 && B == 2) {
    if (0)
      cout << n - 1 << "\n";
    else
      cout << 0 << "\n";
    return;
  }
  if (A == n) {
    if (0)
      cout << n - 1 << "\n";
    else
      cout << 0 << "\n";
    return;
  }
  if (A == n - 1) {
    if (0)
      cout << n - 1 << "\n";
    else
      cout << 0 << "\n";
    return;
  }
  if (A < B) {
    if (a == "right" && b == "left") {
      if ((A + B + 1) % 2)
        cout << n - 1 << "\n";
      else
        cout << 0 << "\n";
      return;
    }
    if (a == "left" && b == "left") {
      B -= A - 1;
      A = 1;
      if (A == 1 && B == 1) {
        if (1)
          cout << n - 1 << "\n";
        else
          cout << 0 << "\n";
        return;
      }
      if (A == 1 && B == 2) {
        if (0)
          cout << n - 1 << "\n";
        else
          cout << 0 << "\n";
        return;
      }
      {
        if ((A + B + 1) % 2)
          cout << n - 1 << "\n";
        else
          cout << 0 << "\n";
        return;
      }
    }
    if (a == "right" && b == "right") {
      A += n - B;
      B = n;
      if (A == n) {
        if (0)
          cout << n - 1 << "\n";
        else
          cout << 0 << "\n";
        return;
      }
      if (A == n - 1) {
        if (0)
          cout << n - 1 << "\n";
        else
          cout << 0 << "\n";
        return;
      }
      {
        if ((A + B + 1) % 2)
          cout << n - 1 << "\n";
        else
          cout << 0 << "\n";
        return;
      }
    }
    if (a == "left" && b == "right") {
      long long t = max(A - 1, n - B);
      A -= t;
      if (A < 1) A = 2 - A;
      B += t;
      if (B > n) B = 2 * n - B;
      if (A == 1 && B == 1) {
        if (1)
          cout << n - 1 << "\n";
        else
          cout << 0 << "\n";
        return;
      }
      if (A == 1 && B == 2) {
        if (0)
          cout << n - 1 << "\n";
        else
          cout << 0 << "\n";
        return;
      }
      if (B == n && A == n) {
        if (0)
          cout << n - 1 << "\n";
        else
          cout << 0 << "\n";
        return;
      }
      if (B == n && A == n - 1) {
        if (1)
          cout << n - 1 << "\n";
        else
          cout << 0 << "\n";
        return;
      }
      {
        if ((A + B + 1) % 2)
          cout << n - 1 << "\n";
        else
          cout << 0 << "\n";
        return;
      }
    }
  } else if (A == B) {
    x = A - 1;
    y = n - x - 1;
    if (a == "left" && b == "right") {
      if (0)
        cout << n - 1 << "\n";
      else
        cout << 0 << "\n";
      return;
    }
    if (a == "left" && b == "left") {
      if (1)
        cout << n - 1 << "\n";
      else
        cout << 0 << "\n";
      return;
    }
    if (a == "right" && b == "right") {
      if (0)
        cout << n - 1 << "\n";
      else
        cout << 0 << "\n";
      return;
    }
    if (a == "right" && b == "left") {
      if (1)
        cout << n - 1 << "\n";
      else
        cout << 0 << "\n";
      return;
    }
  }
}
signed main() {
  long long JYZ;
  JYZ = read();
  while (JYZ--) DOIT();
}
