Robert W Floyd 是一位美国计算机科学家，曾获得图灵奖。在 ACM-ICPC 社区中，他最著名的工作大概是 Floyd-Warshall 算法，该算法可以高效地寻找全源最短路径和传递闭包。它有很多应用，其中许多都非常有用，但下面要说的这个并不是其中之一。

Stitches 是 Darkshire 的梦魇。它沿着路径散发出一种恶臭的胆汁，这种胆汁气味难闻、令人作呕，并且会使你在其中行走时速度降低 35%。简而言之，你不想站在这些胆汁里。随着 Stitches 的移动，它可能会将地图切割成几个分离的区域。如果一个人无法在不穿过 Stitches 胆汁的情况下从一个区域到达另一个区域，那么这两个区域就是分离的。Stitches 总是沿着单一方向（上、下、左或右）移动一个单位长度，然后决定是否改变方向。为了给 Darkshire 带来和平，英雄们会尽快杀死它。你可以假设 Stitches 最多只会排放 2048 个单位长度的胆汁，因为英雄们不会允许它走得更远。

不幸的是，Stitches 的胆汁在它死后并不会消失。作为 Darkshire 的市长，你想要确定在 Stitches 走过之后，地图被分成了多少个分离的区域。那么，我们如何用 Floyd-Warshall 算法来解决这个问题，以及为什么它不适用呢？嗯，由于 Stitches 的移动方式，我们可以想象它是在一个 $4098 \times 4098$ 的方格网的边上行走。Stitches 从网格中心开始行走，因此它永远不会触及边界。这样可以很容易地将地图转换为一个图，如果 Stitches 没有走过连接两个相邻方格的边，那么这两个方格就是连通的。在运行 Floyd-Warshall 算法后，我们可以很容易地确定两个方格是否在同一个区域内。然后，只需使用并查集数据结构来统计区域的数量即可。然而，由于 Darkshire 不是一个小镇，网格上可能有超过 1600 万个方格，这种方法根本不够快。除非你有青铜龙 Chromie（时间守护者）的帮助。请找到一种更好的方法来解决这个问题。再次声明，不允许利用青铜龙作弊。

输入格式

第一行包含一个整数 $T$ ($T \le 30$)，表示测试用例的数量。对于每个测试用例，Stitches 的移动序列将在一行中给出，其中 ‘U’ 表示向上，‘D’ 表示向下，‘L’ 表示向左，‘R’ 表示向右。序列长度不超过 2048。

输出格式

输出一行，包含分离区域的数量。

样例

输入 1

4
LURD
LUDR
LDRDRURRDLUURURD
LLUURRDDRULLLLUR

输出 1

2
1
2
5