問題文

U D L R のいずれかの文字からなる列 $C: C_1 \cdots C_{M}$ に対して、$xy$-座標平面の原点 $(0, 0)$ から出発し、格子点を以下のように移動する:

• $C_m$ が U なら $y$-座標が$1$増える方向に移動
• $C_m$ が D なら $y$-座標が$1$減る方向に移動
• $C_m$ が L なら $x$-座標が$1$減る方向に移動
• $C_m$ が R なら $x$-座標が$1$増える方向に移動

ただし、U と D 及び L と R の個数がそれぞれ等しく、最終的に原点 $(0, 0)$ に戻ってくるものとする。このような文字列 $C$ を「ループ」と呼ぶ。
この格子点の移動経路の変更を、ループ $C$ に対する操作として以下のように定義する:

1. $C$ のどこか一ヶ所の部分列 LR, RL, UD, DU のいずれかを取り除く
2. $C$ のどこか一ヶ所に LR, RL, UD, DU のいずれかを挿入する
3. 後述の条件を満たすときに限り、$C$ のどこか一ヶ所の部分列 $HV$ を $VH$ に書き換える （$H$ は L, R のいずれか、$V$ は U, D のいずれか）
4. 後述の条件を満たすときに限り、$C$ のどこか一ヶ所の部分列 $VH$ を $HV$ に書き換える （$H$ は L, R のいずれか、$V$ は U, D のいずれか）

3, 4 の書き換え操作の条件について説明する。3, 4 の書き換え操作は、移動経路の変更時に格子点を頂点に持つ一辺の長さが1の正方形をまたぐ必要がある。
例えばループ $C$ の RU という部分列を UR に書き換えてループ $C'$ にするとき、下図の斜線部分の正方形をまたぐ:

この正方形に $(0.5, 0.5), (-0.5, 0.5)$ のどちらも含まれていないとき、かつそのときに限り、書き換えを許可する。

ループ $C$ に対する書き換え操作を何度か行うことで、空列からなるループに書き換えられるときループ $C$ は「null-ホモトピック」であるということにしよう。
問題から与えられる $N$ 個のループ $C^1, \dots, C^N$ のうち、null-ホモトピックなものの個数を出力せよ。

背景

この問題は、(折れ線で与えられた) $\mathbb{R}^2 - \{ (\pm 0.5, 0.5) \}$ 内のループが null-ホモトピックであるかを判定させる問題である（数学的なホモトピーの定義と同値であることが示せる）。
ここでは格子点の移動を書き換えるという方法でホモトピーを定義したが、数学ではもっと一般化して、曲線を「連続的に変形できるか」を考える。
例えば、始点と終点がそれぞれ同じであるような平面上の曲線 $f_0, f_1 : [0, 1] \rightarrow \mathbb{R}^2$ を考える。$f_0$ と $f_1$ の間に、$t \in [0, 1]$ で「連続的に」パラメータ付けされた、始点と終点がそれぞれ同じであるような曲線 $f_t : [0, 1] \rightarrow \mathbb{R}^2$ で $f_0$ から $f_1$ へ少しずつ変形していくことができるかを考えてみよう。
そのように連続的な変形が可能であることを「$f_0$, $f_1$ はホモトピックである」という。問題は、「連続的にパラメータ付けされている」とはどういうことかであるが、これは $F(t, s) := f_t(s)$ で定義された関数 $F : [0, 1] \times [0, 1] \rightarrow \mathbb{R}^2$ が連続であると定義されている。

このような問題を考えて何が面白いのだろうか。上では $\mathbb{R}^2$ 内の曲線を考えていたので、あらゆる二つの曲線がホモトピックとなってしまう。しかし、平面からいくつかの点を除いた $\mathbb{R}^2 - \{ p_1, \dots, p_n \}$ 内の曲線のみに制限して考えると途端に話は難しくなる。
例えば $n = 1, \ p_1 = (0, 0)$ として、$f_0, f_1$ をそれぞれ上側と下側の半円弧を通って $(1, 0)$ から $(-1, 0)$ へ向かう曲線としよう。そして、$f_t$ という連続的にパラメータ付けされている $\mathbb{R}^2$ 内の曲線を想像しよう。
このとき、直観的には、どのように $f_0$ を $f_1$ に連続的に変形しても、円内の点 $(0, 0)$ を通ってしまいそうである。
しかし、これを数学的に証明するのは簡単な作業ではない。$n=1$ の場合は、回転数という概念を使うことで分かる。実際、$n=1$ のときホモトピックであることと回転数が等しいことは同値である。

入力

$N \ M$
$C^1_1C^1_2 \dots C^1_{M}$
$\vdots$
$C^N_1C^N_2 \dots C^N_{M}$

$1 \leq NM \leq 2 \times 10^6.$
ただし、$C^n: C^n_1 \cdots C^n_{M}$ の中にある U と D 及び L と R の個数はそれぞれ等しい。

出力

最後に改行してください。

サンプル

2 4
ULDR
URDL

0

2 8
URDLRULD
RULDURDL

2

1 6
RULLDR

0