#include <bits/stdc++.h>
using namespace std;

const int64_t MOD = 1e9 + 7;
const int64_t MOD2 = 998244353;
const int INF = 1e9;
const long long inf = 1LL<<62;

/*
　<方針>
  B-A<=72であり, A-B間で数を選んでも73以上の共通因数をもつことはない.

  (proof)A-B間の数n, m(n != m)が共通因数r>=73を持つとすると
  n = ra_1
  m = ra_2
  が成り立つ. この時n<mとしても一般性を失わず, a_2 > a_1である. すなわち
  m - n = r(a_2 - a_1) > r
  これはB-A <= 72に矛盾する.

  以上の考察から, 持ちうる共通因数は72以下である. しかし, 2^72のbitDPは明らかに間に合わない.
  そこで, 例えば72を共通因数に持つ場合を考えると, これは明らかに2や3を素因数に持っている.
  ようするに, 与えられる数の集合がA-B間の数に限定される場合, 72までの素数を共通として持つかの判定のみでよいということになる.
  72以下の素数は20個しかなく, これの判定だけならbitDPが間に合う.
*/

int main() {
  long long A, B;
  cin >> A >> B;
  vector<int> ep; //72までの素数の集合
  vector<int> pr(73, 1);
  pr[0] = pr[1] = 0;
  for (int i=2; i*i<=72; i++) {
    if (pr[i]) {
      for (int x = i*2; x<=72; x+=i) {
        pr[x] = 0;
      }
    }
  }
  for (int i=2; i<=72; i++) {
    if (pr[i]) ep.push_back(i);
  }
  vector<int> msk(B-A+1); //Aからi番目の数について, 72までの素因数のなかで持っているものをbitで表現
  for (long long x=A; x<=B; x++) {
    for (int i=0; i<20; i++) {
      if (x%ep[i] == 0) msk[x-A] |= 1<<i;
    }
  }
  vector<vector<long long>> dp(B-A+2, vector<long long>(1<<20));
  dp[0][0] = 1;
  for (long long x = A; x <= B; x++) {
    for (int lcm = 0; lcm<(1<<20); lcm++) {
      if (!(lcm & msk[x-A])) {
        dp[x-A+1][lcm | msk[x-A]] += dp[x-A][lcm]; //素因数がかぶっていない場合
      }
      dp[x-A+1][lcm] += dp[x-A][lcm];
    }
  }
  long long ans = 0;
  for (int i = 0; i<(1<<20); i++) {
    ans += dp[B-A+1][i];
  }
  cout << ans << endl;
}

#include <bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define S(x) (int)(x).size()
#define L(x) (int)(x).length()
#define ld long double
#define mem(x,y) memset(x,y,sizeof x)

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int , null_type , less<int> , rb_tree_tag , tree_order_statistics_node_update> ordered_set;

const int mod = 1e9+7;
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;

int dp[1009][1009];

int a[1009],b[1009];

void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	
	for(int i=1;i<=n;i++) dp[i][0]=i;
	for(int i=1;i<=m;i++) dp[0][i]=i;
	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		if(a[i]==b[j])
		{
			dp[i][j]=min(min(dp[i][j-1],dp[i-1][j])+1,dp[i-1][j-1]);
		}
		else
		{
			dp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j],dp[i][j-1])+1);
		}
	}
	cout<<dp[n][m]<<'\n';
}

int main()
{
	IOS
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
}
