Cho hàm số ~f~ với ~n~ tham số xác định như sau:

~f(x_1, x_2, \dots, x_n) = (((x_1 + x_2 + \dots + x_n)^4 + 2 \cdot (x_1 + x_2 + \dots + x_n)^2) \bmod 5) + 1~

Nhiệm vụ của bạn là tính giá trị của biểu thức ~\sum_{x_1=v_1}^{w_1}\sum_{x_2=v_2}^{w_2}\dots\sum_{x_n=v_n}^{w_n} f(x_1, x_2, \dots, x_n)~ trong đó ~v_1, v_2, \dots, v_n~ và ~w_1, w_2, \dots, w_n~ là các giá trị cho trước.

Chẳng hạn, nếu ~n = 3, v_1 = 2, w_1 = 3, v_2 = 10, w_2 = 12, v_3 = 17~ và ~w_3 = 17~, khi đó tổng là ~19~ vì ~f(2,10,17) + f(2,11,17) + f(2,12,17) + f(3,10,17) + f(3,11,17) + f(3,12,17) = 4 + 1 + 4 + 1 + 4 + 5 = 19~.

Giả thiết rằng kết quả thu được luôn không lớn hơn ~1000000~.

Input

Gồm ~1~ dòng chứa số nguyên ~n~ ~(1 \le n \le 1000)~, sau đó là ~n~ cặp số ~v_i, w_i~ với ~0 \le v_i \le w_i \le 100~.

Output

Gồm ~1~ số nguyên duy nhất là tổng cần tính.

Scoring

Sample Input 1

3 2 3 10 12 17 17

Sample Output 1

19