A. FizzBuzz Remixed
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

FizzBuzz is one of the most well-known problems from coding interviews. In this problem, we will consider a remixed version of FizzBuzz:

Given an integer $$$n$$$, process all integers from $$$0$$$ to $$$n$$$. For every integer such that its remainders modulo $$$3$$$ and modulo $$$5$$$ are the same (so, for every integer $$$i$$$ such that $$$i \bmod 3 = i \bmod 5$$$), print FizzBuzz.

However, you don't have to solve it. Instead, given the integer $$$n$$$, you have to report how many times the correct solution to that problem will print FizzBuzz.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case contains one line consisting of one integer $$$n$$$ ($$$0 \le n \le 10^9$$$).

Output

For each test case, print one integer — the number of times the correct solution will print FizzBuzz with the given value of $$$n$$$.

Example
Input
7
0
5
15
42
1337
17101997
998244353
Output
1
3
4
9
270
3420402
199648872
Note

In the first test case, the solution will print FizzBuzz for the integer $$$0$$$.

In the second test case, the solution will print FizzBuzz for the integers $$$0, 1, 2$$$.

In the third test case, the solution will print FizzBuzz for the integers $$$0, 1, 2, 15$$$.