There are a light source, a target point and five mirrors on a two-dimensional plane. Your task is to find out whether a ray that originates from the light source can reach the target point through exactly $0,1,\ldots,5$ reflections.
The light source sends rays to all directions. All mirrors are double-sided, i.e., a ray will reflect from both sides of the mirror.
The first input line contains an integer $t$: the number of test cases. After this, the test cases are described as follows:
First there are two lines that specify the locations of the light source and the target point. Both lines contain two integers $x$ and $y$, meaning that the location of the point is $(x,y)$.
Finally, there are five lines that specify the locations of the mirrors. Each line contains four integers $x_1$, $y_1$, $x_2$ and $y_2$, meaning that a there is a mirror between points $(x_1,y_1)$ and $(x_2,y_2)$.
For each test case, output a binary string $x_0x_1\ldots x_5$ where $x_i$ is $1$ if light reaches the target through $i$ reflections.
- $1 \le t \le 10$
- all input coordinates are between $0 \ldots 10^9$
- the result does not change if the input coordinates are changed by at most one
- no three input points are collinear
- no mirrors intersect
317000000 661000000 388000000 682000000
533000000 116000000 464000000 126000000
523000000 829000000 350000000 830000000
808000000 928000000 837000000 903000000
455000000 626000000 395000000 650000000
The following figures show the setting in the example, and the areas that are reachable through $0,1,\ldots,5$ reflections: