Оптимизация линейного поиска

Question

У меня есть проблема, которая заключается в следующем: вам дают строку s, состоящую только из двух символов "a" и "b", и целое число n. Рассмотрим строку t, которая является результатом объединения n копий s. например, если s равно aba, а n равно 2, то t равно abaaba (то есть s*2). Пожалуйста, как я могу найти количество подстрок, в которых значение 'a' строго больше, чем значение 'b'. Для приведенного выше примера это пять причин: "а", "аба", "абаа", "абааб", "абааба". Линейный поиск, как и следовало ожидать, дает вердикт TLE.(Мой код ниже делает именно это)

    for _ in xrange(int(raw_input())):
    c = 0
    s, n = raw_input().split(); n = int(n)
    ss = s * n
    h = 0
    while h <= len(ss):
        t = ss[0:h]
        if t.count('a') > t.count('b'):
            c += 1
        h += 1
    print c