Migrated from Lutece 758 P酱的冒险旅途

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

P酱是个可爱的男孩子，有一天他在野外冒险，不知不觉中走入了一块神奇的地方。他在$0$时刻进入这个地方，每一时刻他都只能向某一特定的方向移动长度为1的距离，当然他也可以选择不移动。移动需要花费$1$的时间。

各个时刻他允许移动的方向由一个字符串给出，字符串只包含U、D、L、R四种字符，其中U表示向上（$y$轴正方向）移动，D表示向下（$y$轴负方向）移动，L表示向左（$x$轴负方向）移动，R表示向右（$x$轴正方向）移动。

字符串的第$x$个字符代表了第$x$时刻P酱可以移动的方向，字符串的长度只有$t$，也就是说，超过$t$时刻，P酱就要被邪恶的魔王大爷抓走了~

现在P酱在坐标原点，即$(0,0)$点，而出口在$(x,y)$点，P酱希望在规定的时间$t$内尽快走到出口。帮助P酱在最短的时间内离开这里吧~

Input

第一行包含一个正数 $T$ ($T\leq 100$)，表示数据组数。

接下来每组数据包含两行，第一行包含三个整数 $x,y,t$ ($-10^5\leq x,y\leq 10^5, 0< t\leq 10^5$)；第二行包含一个长度为$t$的字符串，第$i$个字符表示在$i$时刻他能移动的方向，字符串只包含U，D，L，R四种字母。

Output

对于每组数据输出一行，表示P酱到达出口的最早时刻。如果他无法在$t$时刻内到达出口，输出-1。

Samples

2
1 -1 5
LDRDR
-2 1 8
RRUDDLRU

3
-1

Note

第一组样例：

1. P酱在$0$时刻位于原点$(0, 0)$，他只能向左移动，但他选择不走。
2. P酱在$1$时刻依然位于原点$(0, 0)$，他只能向下移动，于是他向下移动到了$(0,-1)$
3. P酱在$2$时刻位于$(0,-1)$，他只能向右移动，于是他移动到了出口$(1, -1)$，所以在$3$时刻，P酱离开了这片区域！

Resources

第五届ACM趣味程序设计竞赛第二场（正式赛）