description: 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.
solution: #include <bits/stdc++.h>
  using namespace std;
  using ll = long long;
  using db = long double;
  using str = string;
  using pi = pair<int, int>;
  template <class T>
  using V = vector<T>;
  template <class T, size_t SZ>
  using AR = array<T, SZ>;
  using vi = V<int>;
  using vb = V<bool>;
  using vpi = V<pi>;
  const int MOD = 1e9 + 7;
  const db PI = acos((db)-1);
  mt19937 rng(0);
  template <class T>
  bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0;
  }
  template <class T>
  bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
  }
  template <class T, class U>
  T fstTrue(T lo, T hi, U first) {
    ++hi;
    assert(lo <= hi);
    while (lo < hi) {
      T mid = lo + (hi - lo) / 2;
      first(mid) ? hi = mid : lo = mid + 1;
    }
    return lo;
  }
  struct Eff {
    bool solveRecur(ll N, ll A, ll B, string DA, string DB) {
      if (DA != DB) {
        if (A == 0 || A == N - 1) {
          DA = DB;
          return solveRecur(N, A, B, DA, DB);
        } else if (B == 0 || B == N - 1) {
          DB = DA;
          return solveRecur(N, A, B, DA, DB);
        }
        if (DA == "left") {
          swap(DA, DB);
          A = N - 1 - A;
          B = N - 1 - B;
          return 1 ^ solveRecur(N, A, B, DA, DB);
        }
        if (A < B) {
          swap(A, B);
          N--;
          A--;
          return solveRecur(N, A, B, DA, DB);
        } else if (A == B) {
          A++;
          B--;
          N--;
          A--;
          return solveRecur(N, A, B, DA, DB);
        }
        ll min_dist = min(N - 1 - A, B);
        return solveRecur(N, A + min_dist, B - min_dist, DA, DB);
      }
      map<string, bool> to_bool;
      to_bool["left"] = 0;
      to_bool["right"] = 1;
      map<bool, string> to_str;
      to_str[0] = "left";
      to_str[1] = "right";
      if (DA == "left") {
        DA = to_str[to_bool[DA] ^ 1];
        DB = to_str[to_bool[DB] ^ 1];
        A = N - 1 - A;
        B = N - 1 - B;
        return 1 ^ solveRecur(N, A, B, DA, DB);
      }
      if (A == B) {
        if (A == 0) {
          return 1;
        }
        return 0;
      }
      if (A < B) {
        return solveRecur(N, B, A + 1, DB, DA);
      }
      assert(A > B);
      if ((N + A - B + (N & 1)) % 2 == 0) {
        return 0;
      }
      return 1;
    }
    void solveTestCase() {
      ll N, A, B;
      cin >> N >> A >> B;
      string DA, DB;
      cin >> DA >> DB;
      if (solveRecur(N, A, B, DA, DB)) {
        cout << N - 1 << "\n";
      } else {
        cout << 0 << "\n";
      }
    }
    void solve() {
      int T;
      cin >> T;
      for (int t = 1; t <= T; t++) {
        solveTestCase();
      }
    }
  };
  int main() {
    cin.tie(0)->sync_with_stdio(0);
    Eff e;
    e.solve();
  }
  