Html – Drupal Override Custom Menu Template

I created a custom menu called "sub-top-nav" and now I'd like to override the html output. In particular I would like to add an unique class to each item like.

This is how it looks atm:

<div class="clear-block block block-menu" id="block-menu-menu-sub-top-nav">
    <div class="content">
    <ul class="menu">
      <li class="leaf first"><a title="Test 1" href="/test1">Test 1</a></li>
      <li class="leaf"><a title="Test 2" href="/test2">Test 2</a></li>
      <li class="leaf active-trail"><a class="active" title="Test 3" href="/test3">Test 3</a></li>
      <li class="leaf last"><a title="Test 4" href="/test4">Test 4</a></li>
    </ul>
  </div>
</div>

And I'd like to change it into:

<div class="clear-block block block-menu" id="block-menu-menu-sub-top-nav">
  <div class="content">
    <ul class="menu">
      <li class="leaf test1 first"><a title="Test 1" href="/test1">Test 1</a></li>
      <li class="leaf test2"><a title="Test 2" href="/test2">Test 2</a></li>
      <li class="leaf test3 active-trail"><a class="active" title="Test 3" href="/test3">Test 3</a></li>
      <li class="leaf test4 last"><a title="Test 4" href="/test4">Test 4</a></li>
    </ul>
  </div>
</div>

This would give me more styling power.
Any idea how that works?

Thanks in advance!