void solve()
{
	int k, l1, r1, l2, r2;
	cin >> k >> l1 >> r1 >> l2 >> r2;
	int k1 = 1, ans = 0;
	for(int i = 0;i <= 50; i++){
		if(i!=0){
			k1 *= k; 
		}
// 遍历k的n次方
		if(l1 * k1 > r2){
			break;
		}
		if(r1 * k1 < l2){
			continue;
		}
		int x = 0, y = 0;
		int l = l1, r = r1;
		while(l < r){
			int mid = l + r >> 1;
			if(mid * k1 >= l2){
				r = mid;
			}
			else{
				l = mid + 1;
			}
		}
        //找出>=l2的第一个数
		x = l;
		l = l1, r = r1;
		while(l < r){
			int mid = l + r + 1 >> 1;
			if(mid*k1 <= r2){
				l = mid;
			}
			else{
				r = mid - 1;
			}
		}
        // 找出<=r2的第一个数
		y = l;
		ans += y - x + 1;
	}
	cout << ans << "\n";
}

void solve() {
    int T, k, l1, r1, l2, r2;
    cin >> k >> l1 >> r1 >> l2 >> r2;
    int sum = 0, k_n = 1;
    for (int i = 0; r2 / k_n >= l1; i++) {
        sum += max(0ll, min(r1, r2 / k_n) - max(l1, (l2 - 1) / k_n + 1) + 1);
        k_n *= k;
    }
    cout << sum << endl;
}