Learning New Algorithms Every Day

Shak is a new programmer and he knows nothing about algorithms. He has made a plan and decided to learn a new algorithm every day. Saturday and Sunday are specials. He will learn one extra algorithm these days.

Today is Wednesday. Shak is going to start today. He wants to know how many algorithms he will learn exactly after N days.

Input

First line contains an integer $T (1 \leq T \leq 100)$, denoting the number of testcases.

Each testcase contains an integer $N$, denoting the number of days.

Subtask

• Subtask 1 (10 points): $1 \leq N < 2^{10}$
• Subtask 2 (70 points): $1 \leq N < 2^{63}$
• Subtask 3 (20 points): $1 \leq N < 2^{100}$

Output

For each testcase, print the answer in seperate lines.

Sample

Input	Output
3 3 4 7	3 5 9