本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden ☆ before use]

1296. A. Good Coin Denomination


Description

Different countries use different coin denominations. For example, the USA uses 1, 5, 10, and 25. A desirable property of coin denominations is to have each coin at least twice the amount of its previous coin in sorted order. For example, the USA  denominations have this property, but the coin denominations {1, 5, 6} do not (6 is not at least twice 5).


The Problem:
Given the coin denominations, you are to determine if the set has the above property.

Input

The first input line contains a positive integer, n, indicating the number of denomination sets to check. The sets are on the following n input lines, one set per line. Each set starts with an integer d (1 ≤ d ≤ 10), which is a count of various coin amounts in the set; this is followed by d distinct positive integers (each less than 1,000) giving each coin amount (assume the coin amounts are given in increasing order).

Output

For each set of coin denominations, output a single integer on a line by itself indicating whether or not the set has the above property. Output the integer 0 (zero) if the set has the property and 1 (one) if it does not.

Samples

Input Copy
2
4 1 5 10 25
3 1 5 6
Output
0
1

Source

UCF2017 PRACTICE
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1033. UCF 2017 Practice
My history solutions

You didn't submit any solution!
Submit your solution

Login Register