Cho số ~N~ nguyên dương ~1\le N \le{10}^{10}~.

Yêu cầu: Đếm số lượng số nguyên dương là bội của ~3~ hoặc ~5~ trong phạm vi từ ~1~ đến ~N~.

INPUT

Đọc từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất chứa số nguyên ~T~ (~1 ≤ T ≤ 100~) cho biết số bộ dữ liệu đầu vào;
• Tiếp theo ~T~ dòng, mỗi dòng chứa một số nguyên dương ~N~.

OUTPUT

• Gồm ~T~ dòng, mỗi dòng tương ứng với mỗi bộ dữ liệu đầu vào, in ra kết quả bài toán.

SAMPLE INPUT 1

3
3
5
10

SAMPLE OUTPUT 1

1
2
5

SUBTASKS

• ~90\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~1 ≤ N ≤ 10^6~
• ~10\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~10^6 < N \le 10^{10}~.

Cho N ~(1 ≤ N ≤ 20)~ phương trình bậc nhất có dạng: ~ax + b = 0~ ~(a ≠ 0)~, hai số nguyên ~a~, ~b~ ~(\left|a\right|,\left|b\right|\le{10}^{12})~ được gọi là hệ số của phương trình, ~x~ là ẩn số.

Yêu cầu: Hãy đếm số lượng phương trình có nghiệm nguyên dương, đồng thời nghiệm đó là số nguyên tố.

INPUT

Đọc từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất chứa số nguyên dương ~N~;
• ~N~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~a~ và ~b~, cách nhau một khoảng trắng.

OUTPUT

• Xuất ra màn hình một số nguyên là số lượng phương trình có nghiệm thỏa mãn yêu cầu bài toán.

SAMPLE INPUT 1

3
1 -3
12 -6
-50 -100

SAMPLE OUTPUT 1

1

Cho hai số nguyên dương ~P~ và ~S~ (~S~ không chứa số ~0~), biết số lượng chữ số của ~S~ không vượt quá số lượng chữ số của ~P~, nếu gọi ~N~ là số lượng chữ số của ~P~ thì ~1 ≤ N ≤ 10^5~.

Yêu cầu: Tìm số nguyên dương lớn nhất không chứa các chữ số thuộc ~S~ nhưng bé hơn hoặc bằng ~P~.

INPUT

Đọc từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất chứa số nguyên dương ~P~;
• Dòng thứ hai chứa số nguyên dương ~S~.

OUTPUT

• Xuất ra màn hình một số nguyên dương lớn nhất (không chứa số ~0~ ở đầu) thỏa mãn yêu cầu bài toán, nếu không có số nào thỏa mãn yêu cầu thì xuất ra màn hình số ~-1~.

SAMPLE INPUT 1

2024
23

SAMPLE OUTPUT 1

1999

Giải thích:

• Số lớn nhất không chứa chữ số ~2~ và ~3~ thuộc ~S~ nhưng bé hơn hoặc bằng ~P =~ 2024 là 1999

SUBTASKS

• ~70\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~1 ≤ N ≤ 8~;
• ~30\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~8 < N ≤ 10^5~.

Cho trước hai số nguyên dương ~N, K~ ~(1 ≤ N ≤ 10^5, 1 ≤ K ≤ 10^9)~ và dãy gồm N số nguyên dương ~a_1,\ a_2,\ \ldots,a_N~.

Dãy con gồm các phần tử liên tiếp kề nhau thuộc dãy ~a_1,\ a_2,\ \ldots,a_N~ có dạng ~\mathrm{a}_\mathrm{u}\mathrm{\mathrm{,\ }}\mathrm{a}_{\mathrm{u+1}}\mathrm{,\ }\mathrm{a}_{\mathrm{u+2}}\mathrm{,\ldots,\ }\mathrm{a}_\mathrm{v} \mathrm{(1\ \le\ u \le v \le N)}~, độ dài của dãy con gồm các phần tử liên tiếp kề nhau bằng số lượng phần tử của dãy.

Yêu cầu: Tìm số nguyên dương ~L~ là độ dài lớn nhất, sao cho tất cả các dãy con gồm các phần tử liên tiếp kề nhau có độ dài ~L~, thuộc dãy ~a_1,\ a_2,\ \ldots,a_N~ đều có tổng các phần tử bé hơn hoặc bằng ~K~.

INPUT

Đọc từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất gồm hai số nguyên dương ~N~ và ~K~;
• Dòng thứ hai chứa N số nguyên dương ~a_1,\ a_2,\ \ldots,a_N (0 < a_i ≤ 10^5, 1≤ i ≤ N)~;
• Các số trên một dòng cách nhau một khoảng trắng.

OUTPUT

• Xuất ra màn hình một số nguyên dương ~L~ là độ dài của dãy con dài nhất thỏa mãn yêu cầu bài toán, nếu không có dãy con nào thỏa mãn yêu cầu thì xuất ra màn hình số ~-1~.

SAMPLE INPUT 1

5 10
1 2 3 4 5

SAMPLE OUTPUT 1

2

Giải thích:

• ~N = 5~, ~K = 10~, dãy ~\{1; 2; 3; 4; 5\}~ có các dãy con liên tiếp kề nhau có độ dài ~L = 2~ là ~\{1; 2\}~, ~\{2; 3\}~, ~\{3; 4\}~, ~\{4; 5\}~ đều có tổng các phần tử bé hơn ~K~, các dãy con liên tiếp kề nhau có độ dài ~L = 3~ là ~\{1; 2; 3\}~, ~\{2; 3; 4\}~, ~\{3; 4; 5\}~ trong đó có dãy con ~\{3; 4; 5\}~ có tổng các phần tử lớn hơn ~K~ nên ~L = 3~ không thỏa mãn yêu cầu bài toán, vậy ~L = 2~ thỏa mãn yêu cầu bài toán.

SUBTASKS

• ~30\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~1 \le N \le 10^2;~
• ~30\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~10^2 \le N \le 10^3;~
• ~40\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~10^3 \le N \le 10^5~

Cho số nguyên dương N và dãy số nguyên ~a_1, a_2, a_3,…, a_N~.

Yêu cầu:

• Với mỗi chỉ số ~x~ ~(1\le x\le N)~, hãy tính ~c\left(x\right)~ là số lượng những bộ ba chỉ số ~\left(i,\ j,\ k\right)~ thỏa mãn đồng thời hai điều kiện:
  • ~1 ≤ i < j < k < x~ (~i, j, k, x~ là những số nguyên dương)
  • ~a_i + a_j + a_k = a_x~

Ví dụ: Cho ~N=5~ dãy gồm ~5~ phần tử: ~\{-5; 7; 6; -5; 8\}~, với các chỉ số ~x = 1, 2, 3, 4~ không có bộ ba (~i, j, k~) nào thỏa mãn nên ~c(1) = 0~, ~c(2) = 0~, ~c(3) = 0~, ~c(4) = 0~, với chỉ số ~x = 5~ có ~a_5 = a_1 + a_2 + a_3 = -5 + 7 + 6 = 8, a_5 = a_2 + a_3 + a_4 = 7 + 6 + (-5) = 8~ nên ~c(5) = 2~.

INPUT

Đọc từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất chứa số nguyên dương ~N~ ~(1 \le N \le5000)~;
• Dòng thứ hai chứa ~N~ số nguyên ~a_1,a_2,\ldots,a_N~ ~(\left|a_i\right|\le{10}^6, 1 ≤ i ≤ N)~.

OUTPUT

• Xuất ra màn hình một dòng duy nhất gồm ~N~ số nguyên ~c(1), c(2), …, c(N)~. Các số trên cùng một dòng ghi cách nhau bởi một dấu cách.

SAMPLE INPUT 1

8
-4 2 -2 3 0 -2 -1 1

SAMPLE OUTPUT 1

0 0 0 0 0 1 2 4

Giải thích:

• ~N = 5~, ~K = 10~, dãy ~\{1; 2; 3; 4; 5\}~ có các dãy con liên tiếp kề nhau có độ dài ~L = 2~ là ~\{1; 2\}~, ~\{2; 3\}~, ~\{3; 4\}~, ~\{4; 5\}~ đều có tổng các phần tử bé hơn ~K~, các dãy con liên tiếp kề nhau có độ dài ~L = 3~ là ~\{1; 2; 3\}~, ~\{2; 3; 4\}~, ~\{3; 4; 5\}~ trong đó có dãy con ~\{3; 4; 5\}~ có tổng các phần tử lớn hơn ~K~ nên ~L = 3~ không thỏa mãn yêu cầu bài toán, vậy ~L = 2~ thỏa mãn yêu cầu bài toán.

SUBTASKS

• ~30\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~\mathrm{1\ \le\ N\ \le\ 50}~;
• ~20\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~\mathrm{50\ <\ N\ \le\ 500}~;
• ~50\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~\mathrm{500\ <\ N\ \le\ 5000}~.