## BPM - Bipartite Permutation

Given a positive integer

Bipartite Permutation (Hard)

**N**, consider any permutation of all the numbers from**1**to**N**. It is required to create two partitions,**P**and_{1}**P**, from these numbers such that_{2}**|sum(P**is minimum, where_{1}) – sum(P_{2})|**sum(X)**denotes the summation of all the numbers in partition**X**. A partition is defined to be a non-empty subset of the permutation. In other words, find the minimum absolute difference between the summation of all the numbers in each partition. Note that you cannot leave out any number, every number from**1**to**N**must be part of exactly one partition.### Input

The first line contains an integer**T**, denoting the number of test cases. Each of the next subsequent**T**lines contain a positive integer**N**.### Constraints

1 ≤ T ≤ 1000 2 ≤ N ≤ 10 ^{9}

### Output

For each test case, first print the case number followed by the minimum absolute difference.### Sample Input

5 2 3 4 5 6

### Sample Output

Case 1: 1 Case 2: 0 Case 3: 0 Case 4: 1 Case 5: 1

### Challenge

Try the harder version here:Bipartite Permutation (Hard)

Added by: | sgtlaugh |

Date: | 2019-11-16 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |

Resource: | Own Problem |