**Working Week solution codeforces** – Your working week consists of 𝑛n days numbered from 11 to 𝑛n, after day 𝑛n goes day 11 again. And 33 of them are days off. One of the days off is the last day, day 𝑛n. You have to decide when the other two are.

## [Solution] Working Week solution codeforces

Choosing days off, you pursue two goals:

- No two days should go one after the other. Note that you can’t make day 11 a day off because it follows day 𝑛n.
- Working segments framed by days off should be as dissimilar as possible in duration. More specifically, if the segments are of size 𝑙1l1, 𝑙2l2, and 𝑙3l3 days long, you want to maximize min(|𝑙1−𝑙2|,|𝑙2−𝑙3|,|𝑙3−𝑙1|)min(|l1−l2|,|l2−l3|,|l3−l1|).

Output the maximum value of min(|𝑙1−𝑙2|,|𝑙2−𝑙3|,|𝑙3−𝑙1|)min(|l1−l2|,|l2−l3|,|l3−l1|) that can be obtained.

The first line of the input contains a single integer 𝑡t (1≤𝑡≤10001≤t≤1000) — the number of test cases. The description of test cases follows.

The only line of each test case contains the integer 𝑛n (6≤𝑛≤1096≤n≤109).

## [Solution] Working Week solution codeforces

Output one integer — the minimum possible obtained value.

0 1 342

## [Solution] Working Week solution codeforces

In the image below you can see the example solutions for the first two test cases. Chosen days off are shown in purple. Working segments are underlined in green.

In test case 11, the only options for days off are days 22, 33, and 44 (because 11 and 55 are next to day 𝑛n). So the only way to place them without selecting neighboring days is to choose days 22 and 44.

## [Solution] Working Week solution codeforces

So the minimum difference is 1=min(1,3,2)=min(|2−1|,|1−4|,|4−2|)1=min(1,3,2)=min(|2−1|,|1−4|,|4−2|). It can be shown that there is no way to make it larger.