#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
bitset<N>vis;
int p[N],cnt;
void ss(int n){
	vis[0]=vis[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]) p[++cnt]=i;
		for(int j=1;j<=cnt&&i*p[j]<=n;j++){
			vis[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}
}
ll dp[1<<20];
int main(){
	ss(72);
	ll A,B;scanf("%lld%lld",&A,&B);
	dp[0]=1;
	//Print(p,cnt);
	for(ll i=A;i<=B;i++){
		int msk=0;
		for(int j=1;j<=cnt;j++) if(i%p[j]==0) msk|=(1<<(j-1));
		for(int j=0;j<(1<<cnt);j++)
			if(!(msk&j)) dp[msk|j]+=dp[j];
	}
	ll s=0;
	for(int i=0;i<(1<<cnt);i++) s+=dp[i];
	printf("%lld\n",s);
	return 0;
}

#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lb;
#define rep(i, f, t) for(int i = f; i <= t; i ++)
#define urep(i, f, t) for(int i = f; i >= t; i --)
#define pb push_back
#define eb emplace_back
#define pq priority_queue
#define umap unordered_map
#define addr(v) v.begin(), v.end()
#define uaddr(v) v.rbegin(), v.rend()
#define mst(arr, val) memset(arr, val, sizeof arr)
#define qstream std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//when qstream exists , cout and printf can't be used together
//
#define ls(t) (t << 1)
#define rs(t) (t << 1 | 1)
#define lowbit(x) ((x) & (-(x)))
#define ceil_div(a, b) ((a) + (b) - 1) / (b)
const ll INF = 1e18 + 7;
const int inf = 0x3f3f3f3f;
const int maxn = 1050;
const int Maxn = 5e5 + 5;
const int mod = 1e9 + 7;
const int MOD = 100003;
const int Mod = 998244353;
const int D = 233;//HASH
const double PI = acos(-1.0);
// tips: i int for_loop i*i can't be used for long long 

int n, m;

struct Edge {
	int to, next;
	char w;
}e[Maxn];

int head[maxn], id;

struct nd {
	int a, b;
};

int dis[maxn][maxn];

void add(int u, int v, char w) {
	e[id].to = v;
	e[id].w = w;
	e[id].next = head[u];
	head[u] = id ++;
}

queue<nd> q;

int main() {
	qstream;
	mst(dis, inf);
	mst(head, -1);
	cin >> n >> m;
	rep(i, 1, m) {
		int u, v;
		char w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	rep(i, 1, n) {
		dis[i][i] = 0;
		q.push({i, i});
	}
	rep(j, 1, n) {
		for(int i = head[j]; i != -1; i = e[i].next) {
			int v = e[i].to;
			if(j >= v) continue;
			dis[j][v] = dis[v][j] = 1;
			q.push({j, v});
		}
	}
	while(!q.empty()) {
		int x = q.front().a, y = q.front().b;
		q.pop();
		//cout << x << " " << y << endl;
		for(int i = head[x]; i != -1; i = e[i].next) {
			int tx = e[i].to;
			for(int j = head[y]; j != -1; j = e[j].next) {
				int ty = e[j].to;
				if(e[i].w == e[j].w && tx != ty) {
					if(dis[tx][ty] > dis[x][y] + 2) {
						dis[ty][tx] = dis[tx][ty] = dis[x][y] + 2;
						q.push({tx, ty});
					}
				}
			}
		}
	}
	cout << (dis[1][n] == inf ? -1 : dis[1][n]) << endl;
	// #ifndef ONLINE_JUDGE
	//     system("pause");
    // #endif
    return 0;
}
