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 <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

#define ff              first
#define ss              second
#define ll              int64_t
#define ld              long double
#define nl              cout<<"\n"
#define all(v)          v.begin(),v.end()
#define mset(a,v)       memset((a),(v),sizeof(a))
#define forn(i,a,b)     for(int64_t i=int64_t(a);i<int64_t(b);++i)
#define forb(i,a,b)     for(int64_t i=int64_t(a);i>=int64_t(b);--i)
#define fastio()        ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define mod         1'000'000'007
#define mod2        998'244'353 
#define inf         1'000'000'000'000'007
#define pi          3.14159265358979323846

template<class key,class cmp=std::less<key>>
using ordered_set=tree<key,null_type,cmp,rb_tree_tag,tree_order_statistics_node_update>;

template<class L,class R> ostream& operator<<(ostream& out,pair<L,R> &p)        {return out<<"("<<p.ff<<", "<<p.ss<<")";}
template<class T> ostream& operator<<(ostream& out,vector<T> &v)                {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,deque<T> &v)                 {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,set<T> &s)                   {out<<"{";for(auto it=s.begin();it!=s.end();++it){if(it!=s.begin())out<<", ";out<<*it;}return out<<"}";}
template<class L,class R> ostream& operator<<(ostream& out,map<L,R> &m)         {out<<"{";for(auto it=m.begin();it!=m.end();++it){if(it!=m.begin())out<<", ";out<<*it;}return out<<"}";}

void dbg_out() {cerr<<"]\n";}
template<typename Head,typename... Tail> 
void dbg_out(Head H,Tail... T) {cerr<<H;if(sizeof...(Tail))cerr<<", ";dbg_out(T...);}
#ifdef LOCAL
	#define dbg(...) cerr<<"["<<#__VA_ARGS__<<"] = [",dbg_out(__VA_ARGS__)
#else
	#define dbg(...)
#endif

//---------------------------------mars4---------------------------------

class Sieve
{
	ll MAXN;

	void sieve(ll n)        
	{
		forn(i,2,MAXN+1)
			spf[i]=i;
		for(ll i=2;i*i<=n;i++)
		{
			if(spf[i]==i)
			{
				for(ll j=i*i;j<=n;j+=i)
				{
					if(spf[j]==j)
						spf[j]=i;
				}
			}
		}
		forn(i,2,MAXN+1)
		{
			if(spf[i]==i)
				prime.push_back(i);
		}
	}

	public:
	vector<ll> spf;
	vector<ll> prime;

	void init(ll n)
	{
		MAXN=n;
		spf=vector<ll>(MAXN+5);
		sieve(MAXN);
	}
};

int main()
{
	fastio();
	ll z,n,m,t,k,i,j,l,d,h,r;
	Sieve si;
	si.init(1'000'007);
	cin>>n;
	vector<ll> a(n);
	string s;
	for(ll &i:a)
		cin>>i;
	cin>>s;
	vector<vector<pair<ll,ll>>> ind(1'000'007);
	vector<vector<ll>> v(1'000'007);
	vector<ll> mnext(n,n-1);
	forn(i,0,n)
	{
		d=a[i];
		if(s[i]=='/' and a[i]>1)
		{
			mnext[i]=i-1;
			while(d!=1)
			{
				r=si.spf[d];
				d/=r;
				if(!ind[r].empty())
				{
					auto &[pos,cnt]=ind[r].back();
					cnt--;
					if(!cnt)
					{
						if(d%r==0)
							mnext[pos]=min(mnext[pos],i-1);
						ind[r].pop_back();
					}
				}
			}
		}
		else
		{
			while(d!=1)
			{
				r=si.spf[d];
				ll cnt=0;
				while(d%r==0)
				{
					d/=r;
					cnt++;
				}
				ind[r].push_back({i,cnt});
			}
		}
	}
	forb(i,n-2,0)
		mnext[i]=min(mnext[i],mnext[i+1]);
	ll ans=0;
	forn(i,0,n)
		ans+=(mnext[i]-i+1);
	cout<<ans<<"\n";
	cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
	return 0;
}
