#include <bits/stdc++.h>
using namespace std;
#define int long long
const int nax=2e5+100,mod=1e9+7;
int dp[nax][19];
int32_t main()
{
    int t=1;
    //cin>>t;
    while(t--)
    {
        string a;
        cin>>a;
        int k;
        cin>>k;
        set<int> s;
        s.clear();
        for(int i=0;i<a.size();i++)
        {
            for(int j=0;j<17;j++)
            {
                dp[i+1][j]+=dp[i][j]*j;
                dp[i+1][j]%=mod;
                dp[i+1][j+1]+=dp[i][j]*(16-j);
                dp[i+1][j+1]%=mod;
            }
            int num=a[i]-'0';
            if(a[i]>='A')
            num=10+a[i]-'A';
            for(int j=0;j<num;j++)
            {
                if(i==0 and j==0)
                continue;
                if(s.count(j))
                {
                    dp[i+1][s.size()]++;
                    dp[i+1][s.size()]%=mod;
                }
                else
                {
                    dp[i+1][s.size()+1]++;
                    dp[i+1][s.size()+1]%=mod;
                }
            }
            s.insert(num);
            if(i!=0)
            dp[i+1][1]+=15;
        }
        int res=dp[a.size()][k];
        set<char> ss;
        for(int i=0;i<a.size();i++)
        ss.insert(a[i]);
        if(ss.size()==k)
        ++res;
        cout<<res;
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,a,n) for (ll i = a;i<(n);++i)
#define all(v) v.begin(),v.end()
#define bit(n) (1LL<<(n))
#define pu(n) push_back(n)
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define MAXR 100000 //10^5
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};
bool IsPrime(ll num){
    if (num < 2) return false;else if (num == 2) return true;else if (num % 2 == 0) return false; double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2){
        if (num % i == 0)return false;
    }
    return true;
}//???true
ll  gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}//?????
ll lcm(ll a, ll b){
	return (a / gcd(a, b)) * b;
}//?????
uintmax_t combi(unsigned int n, unsigned int r) {
  if ( r * 2 > n ) r = n - r;uintmax_t dividend = 1;uintmax_t divisor  = 1;for ( unsigned int i = 1; i <= r; ++i ) { dividend *= (n-i+1);divisor  *= i;}return dividend / divisor;
}
using Graph = vector<vector<int>>;
/*--------------<<fixed<<setprecision(15)----->>-------------------------------------------------------------------------------------------------------------*/
int main(){
    ll n,m;cin>>n>>m;
    vector<pair<ll,ll>>ab(m);
    rep(i,0,m){ll a,b;cin>>a>>b;ab[i].first=a-1;ab[i].second=b-1;}
    ll k;cin>>k;
    vector<pair<ll,ll>>cd(k);
    rep(i,0,k){ll a,b;cin>>a>>b;cd[i].first=a-1;cd[i].second=b-1;}
    ll ans=0;
    rep(bit,0,(1<<k)){
        vector<ll>dish(n,0);ll cnt=0;
        rep(i,0,k){
            if(bit&(1<<i)){
                dish[cd[i].second]++;
            }
            else{
                dish[cd[i].first]++;
            }
        }
        
        rep(i,0,m){
            bool c=true;
            if(!dish[ab[i].first]>=1)c=false;
            if(!dish[ab[i].second]>=1)c=false;
            if(c)cnt++;
        }
        ans=max(ans,cnt);
        
    }
    cout<<ans;
    return 0;
}