The robot is located on a checkered rectangular board of size n × m (n rows, m columns). The rows in the board are numbered from 1 to n from top to bottom, and the columns — from 1 to m from left to right.

The robot is able to move from the current cell to one of the four cells adjacent by side.

The sequence of commands s executed by the robot is given. Each command is denoted by one of the symbols 'L', 'R', 'D' or 'U', and triggers the movement to left, right, down or up, respectively.

The robot can start its movement in any cell. The robot executes the commands starting from the first one, strictly in the order in which they are listed in s. If the robot moves beyond the edge of the board, it falls and breaks. A command that causes the robot to break is not considered successfully executed.

The robot's task is to execute as many commands as possible without falling off the board. For example, on board 3 × 3, if the robot starts a sequence of actions s="RRDLUU" ("right", "right", "down", "left", "up", "up") from the central cell, the robot will perform one command, then the next command will force him to cross the edge. If the robot starts moving from the cell (2, 1) (second row, first column) then all commands will be executed successfully and the robot will stop at the cell (1, 2) (first row, second column).

<image> The robot starts from cell (2, 1) (second row, first column). It moves right, right, down, left, up, and up. In this case it ends in the cell (1, 2) (first row, second column).

Determine the cell from which the robot should start its movement in order to execute as many commands as possible.

Input

The first line contains an integer t (1 ≤ t ≤ 10^4) — the number of test cases.

The next 2t lines contain descriptions of the test cases.

In the description of each test case, the first line contains two integers n and m (1 ≤ n, m ≤ 10^6) — the height and width of the field that the robot is located on. The second line of the description is a string s consisting solely of characters 'L', 'R', 'D' and 'U' — the sequence of commands the robot executes. The string has a length from 1 to 10^6 commands.

It is guaranteed that the total length of s over all test cases does not exceed 10^6.

Output

Print t lines, each of which contains the answer to the corresponding test case. The answer to the test case are two integers r (1 ≤ r ≤ n) and c (1 ≤ c ≤ m), separated by a space — the coordinates of the cell (row number and column number) from which the robot should start moving to perform as many commands as possible.

If there are several such cells, you may output any of them.

Example

Input


4
1 1
L
1 2
L
3 3
RRDLUU
4 3
LUURRDDLLLUU


Output


1 1
1 2
2 1
3 2
import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public  class Main{
    public static String nextLine(){
        String str="";
        try{
            str = input.readLine().trim();
        }
        catch(IOException e){
            e.printStackTrace();
        }
        return str;
    }
    public static String next() {
        while (!tokenizer.hasMoreTokens())
            try {
                tokenizer=new StringTokenizer(input.readLine().trim());
            } catch (IOException e) {
                e.printStackTrace();
            }
            return tokenizer.nextToken();
        }
    public static int nextInt() {
        return Integer.parseInt(next());
    }
    public static int[] readArray(int n) {
        int[] a=new int[n];
        for (int i=0; i<n; i++) a[i]=nextInt();
        return a;
    }
    public static long nextLong() {
        return Long.parseLong(next());
    }
    static void out(String s){
        output.append(s);
    }
    static void out(int s){
        output.append(s);
    }
    static void out(double s){
        output.append(s);
    }
    static void out(long s){
        output.append(s);
    }
    static void out(int a[]){
        for(int each:a){
            output.append(each);
            output.append(" ");
        }
    }static void out(long a[]){
        for(long each:a){
            output.append(each);
            output.append(" ");
        }
    }
    static void out(boolean a[]){
        for(boolean each:a){
            output.append(each);
            output.append(" ");
        }
    }
    static void out(char a[]){
        for(char each:a){
            output.append(each);
            output.append(" ");
        }
    }
    static void line(){
        output.append(line);
    }
    static void space(){
        output.append(" ");
    }
    static void out(Object a[]){
        for(Object each:a){
            output.append(each.toString());
            output.append(" ");
        }
    }
    static void out(Object s){
        output.append(s.toString());
    }

    static class pair implements Comparable<pair>{
        int a,b;
        pair(int a,int b){
            this.a=a;
            this.b=b;
        }
        pair(){}
        public int compareTo(pair p){
            return this.a-p.a;
        }
        public String toString(){
            return "{"+this.a+","+this.b+"} ";
        }
    }
    static int max(int ...a){
        int max=a[0];
        for(int i=1;i<a.length;i++)
            max=Math.max(max, a[i]);
        return max;
    }
    static int min(int ...a){
        int min=a[0];
        for(int i=1;i<a.length;i++)
            min=Math.min(min, a[i]);
        return min;
    }
    static long max(long ...a){
        long max=a[0];
        for(int i=1;i<a.length;i++)
            max=Math.max(max, a[i]);
        return max;
    }
    static long min(long ...a){
        long min=a[0];
        for(int i=1;i<a.length;i++)
            min=Math.min(min, a[i]);
        return min;
    }
    static int gcd(int a, int b ){
        if(b==0)return a ;
        else return gcd(b,a%b) ;
    }
    static long gcd(long a, long b ){
        if(b==0)return a ;
        else return gcd(b,a%b) ;
    }
    static int binarySearch(int a[],int ele,int l,int h){
        while(l<=h){
            int mid=(l+h)/2;
            if(a[mid]==ele) return mid;
            if(ele<a[mid]) h=mid-1;
            else l=mid+1;
        }
        return -1;
    }
    static int binarySearch(int a[],int ele){
        return binarySearch(a,ele,0,a.length-1);
    }
    static int binarySearch(long a[],long ele,int l,int h){
        while(l<=h){
            int mid=(l+h)/2;
            if(a[mid]==ele) return mid;
            if(ele<a[mid]) h=mid-1;
            else l=mid+1;
        }
        return -1;
    }
    static int binarySearch(long a[],long ele){
        return binarySearch(a,ele,0,a.length-1);
    }
    static int ceil(int a[],int l,int h,int ele){
        int ans=-1;
        while(l<=h){
            int mid=(l+h)/2;
            if(a[mid]>=ele){
                ans=mid;
                h=mid-1;
            }
            else l=mid+1;
        }
        return ans;
      }
    static int floor(int a[],int l,int h,int ele){
        int ans=-1;
        while(l<=h){
            int mid=(l+h)/2;
            if(a[mid]<=ele){
                ans=mid;
                l=mid+1;
            }
            else h=mid-1; 
        }
        return ans;
      }
      static int ceil(long a[],int l,int h,long ele){
        int ans=-1;
        while(l<=h){
            int mid=(l+h)/2;
            if(a[mid]>=ele){
                ans=mid;
                h=mid-1;
            }
            else l=mid+1;
        }
        return ans;
      }
    static int floor(long a[],int l,int h,long ele){
        int ans=-1;
        while(l<=h){
            int mid=(l+h)/2;
            if(a[mid]<=ele){
                ans=mid;
                l=mid+1;
            }
            else h=mid-1; 
        }
        return ans;
      }
    static int floor(int a[],int ele){
        return floor(a, 0, a.length-1, ele);
    }
    static int ceil(int a[],int ele){
        return ceil(a,0,a.length-1,ele);
    }
    static int floor(long a[],long ele){
        return floor(a, 0, a.length-1, ele);
    }
    static int ceil(long a[],long ele){
        return ceil(a,0,a.length-1,ele);
    }
    public static void sort(int a[]){
        Arrays.sort(a);
    }
    public static void sort(long a[]){
        Arrays.sort(a);
    }
    public static void reverse(int a[]){
        int i=0,j=a.length-1;
        while(i<j){
            int temp=a[i];
            a[i]=a[j];
            a[j]=temp;
            i++;
            j--;
        }
    }
    public static void reverse(long a[]){
        int i=0,j=a.length-1;
        while(i<j){
            long temp=a[i];
            a[i]=a[j];
            a[j]=temp;
            i++;
            j--;
        }
    }
    static ArrayList<Integer> seive(int n){
        ArrayList<Integer> l= new ArrayList<Integer>();
        boolean prime[]=new boolean[n+1];
        prime[2]=true;
        for(int i=3;i<=n;i+=2)
            prime[i]=true;
        for(int i=3;i*i<=n;i+=2){
            if(prime[i]){
            for(int j=i*i;j<=n;j+=2*i)
                prime[j]=false;
            }
        }
        l.add(2);
        for(int i=3;i<=n;i+=2)
            if(prime[i]) l.add(i);
        return l;
    }
    static boolean[] seiveArray(int n){
        boolean prime[]=new boolean[n+1];
        prime[2]=true;
        for(int i=3;i<=n;i+=2)
            prime[i]=true;
        for(int i=3;i*i<=n;i+=2){
            if(prime[i]){
            for(int j=i*i;j<=n;j+=2*i)
                prime[j]=false;
            }
        }
       return prime;
    }
    static BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokenizer=new StringTokenizer("");
    static StringBuilder output=new StringBuilder();
    static String line="\n";
    static void setJudge() throws Exception{
    boolean oj = System.getProperty("ONLINE_JUDGE") != null;
    if(oj){
      input=new BufferedReader(new FileReader(new File("input.txt")));
      PrintStream out = new PrintStream(new FileOutputStream("output.txt"));
      System.setOut(out);
    }
    else
      input=new BufferedReader(new InputStreamReader(System.in));
 }
  public static void main(String args[]) throws Exception{
    //  setJudge();
     int t=nextInt();
     //  int t=1;
      while(t>0){
        solve();
        t--;
      }
      System.out.print(output);
  }
  static void solve() throws Exception {
      int x=nextInt(),y=nextInt();
      int ansi=1,ansj=1;
      int i=1,j=1,mini=1,minj=1,maxi=1,maxj=1;
      char c[]=nextLine().toCharArray();
      outer:for(char each:c){
          if(each=='R'){
              j++;
              if(j>y)
                break outer;
          }
          else if(each=='L'){
            j--;
            if(j<=0){
                if(maxj>=y)
                    break outer;
                ansj++;
                j++;
            }

          }
          else if(each=='U'){
              i--;
              if(i<=0){
                  if(maxi>=x) break outer;
                  ansi++;
                  i++;
              }

          }
          else{
            i++;
            if(i>=x)
                break outer;
          }

          mini=min(mini,i);
          minj=min(minj,j);
          maxj=max(maxj,j);
          maxi=max(maxi,i);
      }
      out(ansi);
      space();
      out(ansj);
      line();
  }
}