Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

G. Math, math everywhere

time limit per test

5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputIf you have gone that far, you'll probably skip unnecessary legends anyway...

You are given a binary string and an integer . Find the number of integers *k*, 0 ≤ *k* < *N*, such that for all *i* = 0, 1, ..., *m* - 1

Input

In the first line of input there is a string *s* consisting of 0's and 1's (1 ≤ |*s*| ≤ 40).

In the next line of input there is an integer *n* (1 ≤ *n* ≤ 5·10^{5}).

Each of the next *n* lines contains two space-separated integers *p*_{i}, α_{i} (1 ≤ *p*_{i}, α_{i} ≤ 10^{9}, *p*_{i} is prime). All *p*_{i} are distinct.

Output

A single integer — the answer to the problem.

Examples

Input

1

2

2 1

3 1

Output

2

Input

01

2

3 2

5 1

Output

15

Input

1011

1

3 1000000000

Output

411979884

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/20/2018 04:18:27 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|