Kuzya started going to school. He was given math homework in which he was given an array a of length n and an array of symbols b of length n, consisting of symbols '*' and '/'.

Let's denote a path of calculations for a segment [l; r] (1 ≤ l ≤ r ≤ n) in the following way: 

  * Let x=1 initially. For every i from l to r we will consequently do the following: if b_i= '*', x=x*a_i, and if b_i= '/', then x=(x)/(a_i). Let's call a path of calculations for the segment [l; r] a list of all x that we got during the calculations (the number of them is exactly r - l + 1). 



For example, let a=[7, 12, 3, 5, 4, 10, 9], b=[/, *, /, /, /, *, *], l=2, r=6, then the path of calculations for that segment is [12, 4, 0.8, 0.2, 2].

Let's call a segment [l;r] simple if the path of calculations for it contains only integer numbers. 

Kuzya needs to find the number of simple segments [l;r] (1 ≤ l ≤ r ≤ n). Since he obviously has no time and no interest to do the calculations for each option, he asked you to write a program to get to find that number!

Input

The first line contains a single integer n (2 ≤ n ≤ 10^6).

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^6).

The third line contains n symbols without spaces between them — the array b_1, b_2 … b_n (b_i= '/' or b_i= '*' for every 1 ≤ i ≤ n).

Output

Print a single integer — the number of simple segments [l;r].

Examples

Input


3
1 2 3
*/*


Output


2


Input


7
6 4 10 1 2 15 1
*/*/*//


Output


8
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using ull = unsigned long long;

#define endl '\n'
#define ALL(c) begin(c), end(c)
#define cint(...) int __VA_ARGS__; [](auto&...x){(cin>>...>>x);}(__VA_ARGS__);

int const maxn = 1e6 + 5;
int a[maxn];
int prime[maxn];
int L[maxn];
vector<int> pos[maxn];

inline void add(int x, int l) {
    L[l] = l;
    while (x > 1) {
        pos[prime[x]].push_back(l);
        x /= prime[x];
    }
}

inline void del(int x, int l) {
    if (x == 1) {
        L[l] = l;
        return;
    }
    while (x > 1) {
        if ((int) pos[prime[x]].size() == 0) {
            L[l] = 0;
            return;
        }
        L[l] = min(L[l], pos[prime[x]].back());
        pos[prime[x]].pop_back();
        x /= prime[x];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cint(n)
    for (auto i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (auto i = 2; i < maxn; i++) {
        if (prime[i] == 0) {
            prime[i] = i;
            if (i > 1000) continue;
            for (auto j = i * i; j < maxn; j += i) {
                prime[j] = i;
            }
        }
    }

    char type;
    for (auto i = 1; i <= n; i++)
    {
        cin >> type;
        if (type == '*') add(a[i], i);
        else del(a[i], i);
    }

    ll answer = 0;
    vector<pi> f;
    for (auto i = n; i >= 1; i--)
    {
        int cnt = 1;
        while ((int) f.size() > 0 && f.back().first >= L[i])
        {
            cnt += f.back().second;
            f.pop_back();
        }
        f.emplace_back(L[i], cnt);
        if (L[i] == i) answer += cnt;
    }
    cout << answer;
}
