Cho số nguyên dương ~n~ (~n~ ~\le~ ~10^{18}~), hãy đưa ra số lượng các số từ ~1~ đến ~n~, thoả mãn số đó không chia hết cho bất kỳ số nào trong các số từ ~2~ đến ~10~

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~t~ ~\le~ ~10^5~) là số test của đề bài

~t~ dòng tiếp theo, mỗi dòng chứa số nguyên dương ~n~ (~n~ ~\le~ ~10^{18}~)

OUTPUT

Đưa ra ~t~ dòng, mỗi dòng một số nguyên, là số các số từ ~1~ đến ~n~, thoả mãn số đó không chia hết cho bất kỳ số nào trong các số từ ~2~ đến ~10~

SAMPLE INPUT

1
12

SAMPLE OUTPUT

2

Trên một con đường được chia thành các đoạn thẳng như trên trục số. Trên con đường đó có ~n~ nhà treo đèn lồng đón trung thu. Nhà thứ ~i~ có treo đèn bắt đầu từ vị trí ~s_{i}~ đến vị trí ~d_{i}~. Tổ dân phố muốn tính tổng đoạn đường được bao phủ bởi đèn lồng trên con phố trên (chú ý: hai nhà có thể treo đèn lồng trùng nhau trên một đoạn đường) Em hãy giúp tổ dân phố tính tổng số đoạn đường được bao phủ bởi đèn lồng.

Input:

• Dòng đầu là số ~n~ ~(1 \le n \le 10^6)~

• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số ~s_{i}~ và ~d_{i}~ (~0 ≤ s_{i} \le d_{i} ≤ 2*10^9~ )

Output:

Ghi ra số nguyên duy nhất thỏa mãn yêu cầu đề bài

Sample:

Input:

3
1 3
2 4
3 5

Output:

4

Người ta đo độ giống nhau của hai xâu ~X~, ~Y~ có độ dài bằng nhau là số vị trí mà hai kí tự tương ứng trên hai xâu giống nhau, tức là số chỉ số ~i~ thỏa mãn ~X_i = Y_i~. Ví dụ: ~X = 'avbc'~; ~Y = 'avvv'~ có độ giống nhau bằng ~2~. Cho một xâu ~S~ có độ dài ~n~ và một xâu ~T~ có độ dài ~m (m \le n)~, độ giống nhau giữa xâu ~S~ và xâu ~T~ là tổng số độ giống nhau giữa xâu ~T~ và mọi xâu con gồm các kí tự liên tiếp của ~S~ có độ dài ~m~.

Yêu cầu: Cho hai xâu ~S~ và ~T~. Tính độ giống nhau giữa xâu ~S~ và xâu ~T~.

Input

• Dòng đầu ghi xâu ~T~.
• Dòng thứ ~2~ ghi xâu ~S~.
• Các kí tự trong hai xâu thuộc ~'a' .. 'z'~ và có độ dài không quá ~2.10^6~ kí tự.

Output

• Gồm một số nguyên duy nhất là độ giống nhau giữa xâu ~S~ và xâu ~T~.

Subtask

• Có ~25\%~ số test ứng với ~0 < n ≤ 10^2~
• Có ~25\%~ số test ứng với ~10^2 < n ≤ 10^4~
• Có ~50\%~ số test ứng với ~10^4 < n ≤ 2.10^6~

Sample Input 1

 abaab 
 aababacab

Sample Output 1

12