github.com/captn3m0/codechef.git

---
languages_supported:
    - NA
title: F4
category: NA
old_version: true
problem_code: F4
tags:
    - NA
layout: problem
---
###  All submissions for this problem are available. 

Tomek and his numerous friends are standing in a circle. They are all numbered with consecutive identifiers, from 1 to 1337 in the clockwise direction. Starting from person 1, who says "1", successive people read out successive positive integers. The starting direction is clockwise, and there is rule, that whenever integer is divisible by 7 or contains digit 7, the direction is reversed.

So, the identifiers of the persons who read-out successive numbers, are: 1,2,3,4,5,6,7 (person 7 has just read "7" and reversed the direction),6,5,4,3,2,1,1337 (person 1337 has just read "14" and reversed the direction),1,2,3 (person 3 has just read "17" and reversed the direction),2,1,1337,1336, and so on. Tomek has his favorite number, and he wants to calculate where in the circle he should stand to read that number out loud. Even though he is skilled programmer, he is a bit little lazy and would like you to help him out.

### Input

First, 1 ≤ t ≤ 1000, the number of test cases. Each test case is in a separate line, and contains a positive integer smaller than 10100, representing Tomek's favorite number.

### Output

For each testcase, output one integer, the identifier which Tomek should choose in the circle to read his favorite integer loud.

### Example

<pre><strong>Input:</strong>
3
10
100
1000

<strong>Output:</strong>
4
2
1311
</pre>