120E.md (1398B)
1 Source: https://codeforces.com/problemset/problem/120/E 2 3 E. Put Knight! 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 input.txt 16 17 output 18 19 output.txt 20 21 Petya and Gena play a very interesting game "Put a Knight!" on a chessboard *n* × *n* in size. In this game they take turns to put chess pieces called "knights" on the board so that no two knights could threat each other. A knight located in square (*r*, *c*) can threat squares (*r* - 1, *c* + 2), (*r* - 1, *c* - 2), (*r* + 1, *c* + 2), (*r* + 1, *c* - 2), (*r* - 2, *c* + 1), (*r* - 2, *c* - 1), (*r* + 2, *c* + 1) and (*r* + 2, *c* - 1) (some of the squares may be located outside the chessboard). The player who can't put a new knight during his move loses. Determine which player wins considering that both players play optimally well and Petya starts. 22 23 Input 24 25 The first line contains integer *T* (1 ≤ *T* ≤ 100) — the number of boards, for which you should determine the winning player. Next *T* lines contain *T* integers *n**i* (1 ≤ *n**i* ≤ 10000) — the sizes of the chessboards. 26 27 Output 28 29 For each *n**i* × *n**i* board print on a single line "0" if Petya wins considering both players play optimally well. Otherwise, print "1". 30 31 Examples 32 33 Input 34 35 ``` 36 2 37 2 38 1 39 ``` 40 41 Output 42 43 ``` 44 1 45 0 46 ```