Lucky 7 in the Pocket

BaoBao loves number 7 but hates number 4, so he refers to an integer as a "lucky integer" if is divisible by 7 but not divisible by 4. For example, 7, 14 and 21 are lucky integers, but 1, 4 and 28 are not.

Today BaoBao has just found an integer in his left pocket. As BaoBao dislikes large integers, he decides to find a lucky integer such that and is as small as possible. Please help BaoBao calculate the value of .

Input

There are multiple test cases. The first line of the input is an integer (about 100), indicating the number of test cases. For each test case:

The first and only line contains an integer (), indicating the integer in BaoBao's left pocket.

Output

For each test case output one line containing one integer, indicating the value of .

Sample Input

4
1
7
20
28

Sample Output

7
7
21
35

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF=1e9;
int a[]={7,14,21,35,42,49,63,70,77,91,98,105};
int n;

void solve(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        int res=INF,ans=0;
        for(int i=0;i<12;i++){
            if(a[i]>=n&&res>=abs(n-a[i])){
                res=abs(n-a[i]);ans=a[i];
            }
        }
        printf("%d\n",ans);
    }
}
int main(){
    solve();
    return 0;
}