Santa Claus has Robot which lives on the infinite grid and can move along its lines. He can also, having a sequence of m points p_1, p_2, ..., p_{m} with integer coordinates, do the following: denote its initial location by p_0. First, the robot will move from p_0 to p_1 along one of the shortest paths between them (please notice that since the robot moves only along the grid lines, there can be several shortest paths). Then, after it reaches p_1, it'll move to p_2, again, choosing one of the shortest ways, then to p_3, and so on, until he has visited all points in the given order. Some of the points in the sequence may coincide, in that case Robot will visit that point several times according to the sequence order.

While Santa was away, someone gave a sequence of points to Robot. This sequence is now lost, but Robot saved the protocol of its unit movements. Please, find the minimum possible length of the sequence.


-----Input-----

The first line of input contains the only positive integer n (1 ≤ n ≤ 2·10^5) which equals the number of unit segments the robot traveled. The second line contains the movements protocol, which consists of n letters, each being equal either L, or R, or U, or D. k-th letter stands for the direction which Robot traveled the k-th unit segment in: L means that it moved to the left, R — to the right, U — to the top and D — to the bottom. Have a look at the illustrations for better explanation.


-----Output-----

The only line of input should contain the minimum possible length of the sequence.


-----Examples-----
Input
4
RURD

Output
2

Input
6
RRULDD

Output
2

Input
26
RRRULURURUULULLLDLDDRDRDLD

Output
7

Input
3
RLL

Output
2

Input
4
LRLR

Output
4



-----Note-----

The illustrations to the first three tests are given below.

[Image] [Image] [Image]

The last example illustrates that each point in the sequence should be counted as many times as it is presented in the sequence.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = input()
prot = dict()
prot["D"] = "U"
prot["L"] = "R"
prot["R"] = "L"
prot["U"] = "D"
was = set()
ans = 1
for i in range(n):
    if (a[i] not in was):
        if (len(was) == 0):
            was.add(a[i])
        elif len(was) == 1:
            if (prot[a[i]] not in was):
                was.add(a[i])
            else:
                was.clear()
                was.add(a[i])
                ans += 1
        else:
            was.clear()
            was.add(a[i])
            ans += 1
print(ans)

n = int(input())
s = input()
v = ''
h = ''
vs = {'U' , 'D'}
hs = {'L', 'R'}
ans = 1
for i in s:
    if i in vs:
        if v == '':
            v = i
        else:
            if v != i:
                v = i
                ans += 1
                h = ''
    else:
        if h == '':
            h = i
        else:
            if h != i:
                h = i
                ans += 1
                v = '' 
print(ans)


n = int(input())
a = input()
opp = ['UD', 'DU', 'LR', 'RL']

c1 = None
c2 = None

cnt = 0

for i in range(n):
    if c1 is None:
        c1 = a[i]
    elif c1 == a[i] and c2 is None:
        continue
    elif c1 != a[i] and c2 is None:
        if c1 + a[i] in opp:
            cnt += 1
            c1 = a[i]
            c2 = None
        else:
            c2 = a[i]
    elif c1 is not None and c2 is not None and (c1 == a[i] or c2 == a[i]):
        continue
    elif c1 is not None and c2 is not None and (c1 != a[i] and c2 != a[i]):
        cnt += 1
        c1 = a[i]
        c2 = None

print(cnt + 1)

def main():
    n = int(input())
    s = input()
    fr = None
    sc = None
    ans = 0 
    for elem in s:
        if (fr == None):
            fr = elem
            ans += 1
        else:
            if (sc == None):
                if (elem == fr):
                    continue
                else:
                    if (fr == 'L' and elem == 'R') or (fr == 'R' and elem == 'L') or (fr == 'D' and elem == 'U') or (fr == 'U' and elem == 'D'): 
                        ans += 1
                        fr = elem
                        sc = None
                    else:
                        sc = elem
            else:
                if (elem == fr or elem == sc):
                    continue
                else:
                    ans += 1
                    fr = elem
                    sc = None
    print(ans)
main()


n = int(input())
a = input()
s = set()
ans = 0
for j in range(n):
    if a[j] == 'R':
        if 'L' in s:
            
            ans += 1
            s = set()
        s.add(a[j])
        
    elif a[j] == 'L':
        if 'R' in s:
            ans += 1
            s = set()
        s.add(a[j])         
    elif a[j] == 'U':
        if 'D' in s:
            ans += 1
            s = set()
        s.add(a[j]) 
    elif a[j] == 'D':
        if 'U' in s:
            ans += 1
            s = set()
        s.add(a[j])  
    
print(ans+1)

n = int(input())
s = input()
cur = 0
su = 0
while(cur!=n):
    q = set()
    flag = 0
    while(cur!=n and flag == 0):
        if(s[cur]=='R' and 'L' not in q):
            q.add('R')
            cur+=1
        elif(s[cur]=='L' and 'R' not in q):
            q.add('L')
            cur+=1
        elif(s[cur]=='U' and 'D' not in q):
            q.add('U')
            cur+=1
        elif(s[cur]=='D' and 'U' not in q):
            q.add('D')
            cur+=1
        else:
            flag = 1
        if(cur==n):
            flag = 1
    su+=1
print(su)
        


M = int(input())
S = input()
anticmd = {
    'L':'R',
    'R':'L',
    'U': 'D',
    'D': 'U'
}
k = 0
stop = set()
for i in range(M):
    c = S[i]
    if c in stop:
        k += 1
        stop = set()

    stop.add(anticmd[c])

k += 1

print(k)

n=int(input())
s=input()
c=set()
ans=0
ma=['LD','LU','RD','RU']
may=[set(i) for i in ma]
for i in s:
    if not i in c:
        c.add(i)
        if len(c)>1 and not c in may:
            ans+=1
            c=set(i)
if c:
    ans+=1
print(ans)


n = int(input())
string = input()
res = []
r = 0
for i in string:
    if i not in res:
        if len(res) == 2 or len(res) == 0:
            res = [i]
            r += 1
        else:
            if (res[0] in ("U", "D") and i in ("L", "R")) or (i in ("U", "D") and res[0] in ("L", "R")):
                res.append(i)
            else:
                res = [i]
                r += 1

print(r)


n=int(input())
sost=now=''
res=0
cond={'UR','RD','DL','LU','RU','DR','LD','UL'}
for i in input():
	now+=i
	if len(now)==1:
		continue
	if len(now)==2:
		if now[1]==now[0]:
			now=now[1:]
			continue
		if now in cond:
			if sost!='' and (sost[:]!=now and sost[-1::-1]!=now):
				res+=1
				sost=''
				now=now[1:]
			else:
				sost=now
				now=now[1:]
		else:
			res+=1
			sost=''
			now=now[1:]
print(res+1)


n = int(input())
*s, = list(map((lambda x: 'URDL'.find(x)), list(input())))

last = set()
cnt = 0

for i in range(len(s)):
    d = s[i]
    for ld in last:
        if min(abs(ld-d), 4 - abs(ld-d)) > 1:
            cnt += 1
            last = set()
            break
    last.add(d)

print(cnt+1)


n = int(input())
s = input()
inv = {'L': 'R', 'R': 'L', 'D': 'U', 'U': 'D'}

res = 1

i = 0

t = set()
while i < len(s):
    d = s[i]
    if inv[d] in t:
        res += 1
        t = set()
    t.add(d)
    i += 1

print(res)


n = int(input())
s = input()
ans = 1
rl = ''
ud = ''
for i in range(n):
    if s[i] == 'L' or s[i] == 'R':
        if not rl:
            rl = s[i]
        elif rl != s[i]:
            ans += 1
            rl, ud = s[i], 0
    elif s[i] == 'U' or s[i] == 'D':
        if not ud:
            ud = s[i]
        elif ud != s[i]:
            ans += 1
            rl, ud = 0, s[i]
print(ans)

N = int(input())
s = input()
se = set()
count = 1
for i in s:
    if not i in se:
        if len(se)==2:
            count+=1
            se = {i}
        elif len(se)==0:
            se.add(i)
        else:
            if i == 'L' and 'R' in se:
                count+=1
                se = {i}
            elif i == 'R' and 'L' in se:
                count+=1
                se = {i}
            elif i == 'U' and 'D' in se:
                count+=1
                se = {i}
            elif i == 'D' and 'U' in se:
                count+=1
                se = {i}
            else:
                se.add(i)
print(count)


a=int(input())
b=input()
c=[]
k=1
for i in range(a):
    if b[i]=='R' and 'L' in c or b[i]=='L' and 'R' in c or b[i]=='U' and 'D' in c or b[i]=='D' and 'U' in c:
        c=[]
        k+=1
        c.append(b[i])
    if not b[i] in c:
        c.append(b[i])
print(k)

n=int(input())
s=input()
s=list(s)
r,l,u,d=0,0,0,0
points=0
for i in s:
    if(i=='R'):
        r=1
        if(l==1):
            points+=1
            l, u, d = 0, 0, 0
    if (i == 'L'):
        l = 1
        if (r == 1):
            points += 1
            r, u, d = 0, 0, 0
    if (i == 'U'):
        u = 1
        if (d == 1):
            points += 1
            l, r, d = 0, 0, 0

    if (i == 'D'):
        d = 1
        if (u == 1):
            points += 1
            l, u, r = 0, 0, 0
print(points+1)

n = int(input())
s = input()
cnt = 0
up = 0
down = 0
left = 0
right = 0
for i in range(n):
    if s[i] == "U" and down == 0:
        up = 1
    elif s[i] == "U" and down == 1:
        cnt += 1
        up = 1
        down = 0
        left = 0
        right = 0
    if s[i] == "D" and up == 0:
        down = 1
    elif s[i] == "D" and up == 1:
        cnt += 1
        up = 0
        down = 1
        left = 0
        right = 0
    if s[i] == "L" and right == 0:
        left = 1
    elif s[i] == "L" and right == 1:
        cnt += 1
        up = 0
        down = 0
        left = 1
        right = 0
    if s[i] == "R" and left == 0:
        right = 1
    elif s[i] == "R" and left == 1:
        cnt += 1
        up = 0
        down = 0
        left = 0
        right = 1
print(cnt + 1)

n=int(input())
s=input()
i=0
v=0
g=0
kol=0
while i<n:
    a=s[i]
    if a=='U':
        if v==0:
            v=1
        elif v==-1:
            kol+=1
            v=0
            g=0
            i-=1
    elif a=='D':
        if v==0:
            v=-1
        elif v==1:
            kol+=1
            v=0
            g=0
            i-=1
    elif a=='R':
        if g==0:
            g=1
        elif g==-1:
            kol+=1
            v=0
            g=0
            i-=1
    else:
        if g==0:
            g=-1
        elif g==1:
            kol+=1
            v=0
            g=0
            i-=1
    i+=1        
print(kol+1)            
            
    


input()
n = input()
def isok(f,s):
    if (f == "U" or f == "D") and (s == "L" or s == "R"):
        return True
    if (f == "R" or f == "L") and (s == "U" or s == "D"):
        return True
    return False
first = ""
second= ""
res = 0
for i in range(len(n)):
    if not first:
        first = n[i]
    elif first and not second:
        if n[i] == first:
            continue
        elif isok(first,n[i]):
            second = n[i]
        else:
            res += 1
            first = n[i]
            second = ""
    elif first and second:
        if n[i] == first or n[i] == second:
            continue
        else:
            res += 1
            first = n[i]
            second = ""
print(res + 1)
        
        
    


n = int(input())
A = input()
count = 0
B = {"L": 0, "R": 1, "U": 2,"D": 3}
C = {"L": "R", "R": "L", "U": "D","D": "U"}
res = [0, 0, 0, 0]
for i in A:
    if res[B[C[i]]] == 0:
        res[B[i]] += 1
    else:
        count += 1
        res = [0, 0, 0, 0]
        res[B[i]] += 1
if res != [0, 0, 0, 0]:
    count += 1
print(count)

n = int(input())
s = input()
f1 = 0
f2 = 0
res = 0
for i in range(len(s)):
    if(s[i] == "L"):
        if f1 == 0:
            f1 = -1
        if f1 == 1:
            res += 1
            f1 = -1
            f2 = 0
    if(s[i] == "R"):
        if f1 == 0:
            f1 = 1
        if f1 == -1:
            res += 1
            f1 = 1
            f2 = 0
    if(s[i] == "U"):
        if f2 == 0:
            f2 = -1
        if f2 == 1:
            res += 1
            f1 = 0
            f2 = -1
    if(s[i] == "D"):
        if f2 == 0:
            f2 = 1
        if f2 == -1:
            res += 1
            f1 = 0
            f2 = 1
if (f1 != 0 or f2 != 0):
    res += 1
print(res)

n = int(input())
s = input()
mh = ''
mv = ''
count = 0
for e in s:
    if mv == '' and e in ('U', 'D'):
        mv = e
    if mh == '' and e in ('L', 'R'):
        mh = e
    if e in ('U', 'D'):
        if e != mv:
            count += 1
            mv = e
            mh = ''
    if e in ('L', 'R'):
        if e != mh:
            count += 1
            mh = e
            mv = ''
    
print(count+1)


n = int(input())
s = str(input())
k = 1
move = {'R': 'L', 'L': 'R', 'U': 'D', 'D': 'U'}
plus = set()
for i in s:
      if i in plus:
            plus.clear()
            k+=1
      plus|={move[i]}
print(k)