The 2020 ICPC Asia Taipei-Hsinchu Site Programming Contest
A. Right-Coupled Numbers
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

An integer $$$x$$$ is said to be a right-coupled number, if you can find two integers, say $$$0 \le a \leq b \leq x$$$ such that $$$a \times b = x$$$ and $$$\frac{a}{b} \geq 0.5$$$. In this problem, your task is to determine whether a given integer is a right-coupled number or not.

Input

The first line of the input is an integer $$$N$$$ denoting the number of test cases ($$$1 \le N \le 1000$$$). Each test case is in one line, which contains a single integer $$$0 \lt x \lt 2^{15}$$$.

Output

If the given integer $$$x$$$ is a right-coupled number, output $$$1$$$; otherwise, output $$$0$$$. Each is in a single line.

Example
Input
4
66
55
105
150
Output
1
0
0
1

B. Make Numbers
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
1 1 1 1
Output
15
Input
1 1 2 1
Output
32

C. Pyramid
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
3
5 3
5 4
5 5
Output
2
3
2
Input
2
5 1
5 2
Output
0
1

D. Quality Monitoring
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output
Example
Input
5 7
1 0
2 3
1 4
1 2
3 1
3 4
0 4
Output
2

E. A Color Game
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
BBBRRRRRRGGGB 3
Output
Yes
Input
BBBRRRRRRGGGB 4
Output
No

F. Cable Protection
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
4 11
0 1
0 3
0 4
0 5
1 2
1 6
2 3
2 9
3 12
6 7
6 8
9 10
10 11
12 13
12 14
Output
5
Input
3 2
0 1
1 2
0 2
1 3
2 4
Output
2

G. Graph Cards
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
1
2
4 1 2 2 3 3 1 1 4
4 1 2 2 3 3 1 2 4
Output
1
Input
2
2
4 1 2 2 3 3 1 1 4
5 1 2 2 3 3 1 2 4 2 5
3
9 1 2 2 5 5 7 7 6 6 3 3 1 2 4 7 9 9 8
9 1 4 4 2 2 3 3 5 5 7 7 6 6 4 7 8 8 9
9 1 2 2 5 5 4 4 1 4 7 7 8 8 6 8 9 5 3
Output
2
2

H. Optimization for UltraNet
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
3 3
1 2 5
1 3 6
2 3 8
Output
20
Input
5 7
1 2 6
1 3 10
1 4 12
2 4 8
2 5 3
3 4 4
4 5 2
Output
44
Input
5 5
2 5 1
1 2 2
2 3 4
1 3 5
2 4 6
Output
24

I. Critical Structures
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
1
6 6
1 2
2 3
3 4
4 5
5 6
6 1
Output
0 0 1 6
Input
1
6 7
1 2
2 3
3 1
4 5
5 6
6 4
1 4
Output
2 1 1 1

J. Puzzle Game
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Example
Input
3
7 3
ABADCAB
CBB
11 7
ABACCDBADAC
AADCDAC
3 2
ABA
CB
Output
ACDABAB
ABADBACCDAC
NO

K. Number with Bachelors
time limit per test
2 с
memory limit per test
1024 megabytes
input
standard input
output
standard output
Example
Input
6
d 0 10 20
h 0 10 1f
d 1 10
h 1 f
d 1 1000000000
h 1 ffffffffffffffff
Output
10
f
9
e
-
-

L. Save lives or money
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
20
1 2 1
0 0 20 20
20 20 0 20
0 20 0 0
10 15 100
Output
200.0 100 1 1
1
Input
100
5 5 5
0 10 10 0
0 0 0 10
0 0 10 0
0 0 -10 0
0 0 -5 5
0 -10 -10 0
-10 0 -5 5
0 10 -5 5
10 0 0 -10
0 0 0 -10
3 3 5
-5 3 1
-3 5 1
-3 -3 1
3 -3 10
Output
100.0 15 2 2
1 3
Input
33
3 17 3
-4 4 5 4
-4 3 -3 3
3 -3 4 -3
0 1 0 -1
-4 3 -4 -3
-3 -2 -3 3
-2 2 -2 -1
2 1 2 -2
3 2 3 -3
4 3 4 -3
-3 3 4 3
-2 2 3 2
-2 -1 0 -1
0 1 2 1
-3 -2 2 -2
-4 -3 3 -3
-4 -4 5 -4
-4 -4 -4 -3
-4 3 -4 4
5 -4 5 4
1 0 5
-1 0 1
-1 0 1
Output
48.0 5 1 2
1 3

M. Keystroke
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
2
2 1
0 1
0
1 2
1
0 1
Output
1
1
Input
2
2 2
0 1
0 1
1 1
1
1
Output
7
1