{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":" \n \u003cp\u003e\"It\u0027s too quiet,\" David Jr murmured to himself. His space fleet entered the battlefield several minutes ago, but there was no any trace of the enemy. Everyone on the spaceship was waiting for enemy\u0027s attack with great pressure.\u003c/p\u003e \n \u003cp\u003eSuddenly, the alarm sounded. \"Wait, it\u0027s not the enemy.\" David realized, \"it is the instrument fault.\" The reason for instrument fault was found out quickly: The distance between each spaceship calculated by 3-dimensional coordinates of spaceships didn’t correspond with the distance calculated by communication delay. “Every ship gives the same warning, indicating that is not just a simple instrument fault. Well, it can only be explained by ’that thing.\u0027” David believed that enemy had invented “K-Dimensional Foil”, the Ultimate Weapon,and they were just being attacked by that weapon.\u003c/p\u003e \n \u003cp\u003e“K-Dimensional Foil” was a dimensional weapon. It could ascend a region in 3-dimensional space to K-dimensional (K \u0026gt;\u003d 3) space, which might cause great damage to objects in that region. When a spaceship was in K-dimensional space, its coordinate was a K-dimensional coordinate. But its computer only knew the original 3-dimensional coordinate, it could not get the coordinates in other higher dimensions. So, the distance between spaceships calculated by coordinates were not correct. But the actual distances could always be calculated by communication delay. \u003c/p\u003e \n \u003cp\u003eDavid was a cautious man. He had prepared some way to defend the “K-dimensional Foil”. However, he had to know the number of dimensions of the space in which his fleet was. This glorious mission was given to you, the chief technology officer in this fleet.\u003c/p\u003e \n \u003cp\u003eNow, it was your time to make history ……\u003c/p\u003e \n "}},{"title":"Input","value":{"format":"HTML","content":" \n \u003cp\u003eThe first line of the input is an integer T (T \u0026lt;\u003d 100), the number of test cases.\u003c/p\u003e \n \u003cp\u003eFor each test case, the first line contains one integer n (1 \u0026lt;\u003d n \u0026lt;\u003d 50), the number of spaceships in David’s fleet.\u003c/p\u003e \n \u003cp\u003eThen n lines follow. Each line contains three integers x, y, z (-300 \u0026lt;\u003d x, y, z \u0026lt;\u003d 300), the 3-dimentional coordinate of a spaceship.\u003c/p\u003e \n \u003cp\u003eThen n-1 lines follow. The i\u003csup\u003eth\u003c/sup\u003e line contains n - i positive integers. The j\u003csup\u003eth\u003c/sup\u003e \u0026nbsp;integer of the \u0026nbsp;i\u003csup\u003eth\u003c/sup\u003e line is D\u003csub\u003ei,i+j\u003c/sub\u003e \u0026nbsp;(0≤D\u003csub\u003ei,i+j\u003c/sub\u003e≤5000000), which denotes the square(to avoid precision problem) of actual distance between the i\u003csup\u003eth\u003c/sup\u003e spaceship and the (i+j)\u003csup\u003eth\u003c/sup\u003e spaceship which is calculated by communication delay.\u003c/p\u003e \n \u003cp\u003eNotice: The distance in this problem is Euclidean distance. For example, the distance between point (x\u003csub\u003e1\u003c/sub\u003e,y\u003csub\u003e1\u003c/sub\u003e,z\u003csub\u003e1\u003c/sub\u003e,k\u003csub\u003e1\u003c/sub\u003e) and point (x\u003csub\u003e2\u003c/sub\u003e,y\u003csub\u003e2\u003c/sub\u003e,z\u003csub\u003e2\u003c/sub\u003e,k\u003csub\u003e2\u003c/sub\u003e) in 4-dimentional space is sqrt((x\u003csub\u003e1\u003c/sub\u003e-x\u003csub\u003e2\u003c/sub\u003e)\u003csup\u003e2\u003c/sup\u003e+(y\u003csub\u003e1\u003c/sub\u003e-y\u003csub\u003e2\u003c/sub\u003e)\u003csup\u003e2\u003c/sup\u003e+(z\u003csub\u003e1\u003c/sub\u003e-z\u003csub\u003e2\u003c/sub\u003e)\u003csup\u003e2\u003c/sup\u003e+(k\u003csub\u003e1\u003c/sub\u003e-k\u003csub\u003e2\u003c/sub\u003e)\u003csup\u003e2\u003c/sup\u003e ) \u0026nbsp;.\u003c/p\u003e \n "}},{"title":"Output","value":{"format":"HTML","content":" \n \u003cp\u003e\u003cspan\u003eFor each test case, output an integer K, the minimal possible number of dimensions of the new space. If the input can’t fit in any dimensional space, you should print “Goodbye World!”, without quotations. \u003c/span\u003e\u003c/p\u003e \n \u003cp\u003e\u003c/p\u003e \n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \n \u003cpre\u003e3\r\n3\r\n0 0 1\r\n0 0 2\r\n0 0 3\r\n10 20\r\n26\r\n3\r\n1 0 0\r\n2 0 0\r\n3 0 0\r\n3 7\r\n20\r\n3\r\n0 0 0\r\n1 1 1\r\n2 2 2\r\n3 12\r\n3\u003c/pre\u003e \n "}},{"title":"Sample Output","value":{"format":"HTML","content":" \n \u003cpre\u003e5\r\nGoodbye World!\r\n3\r\n\u003c/pre\u003e \n "}},{"title":"Hint","value":{"format":"HTML","content":" \n \u003cp\u003e\u003c/p\u003e \n \u003cp\u003eCase #1: In one possible situation, it’s a 5-dimentional space and the coordinates of these three ships are (0,0,1,0,0), (0,0,2,0,3), (0,0,3,4,0)\u003c/p\u003e \n \u003cp\u003eCase #2: The distances between ship 1 and ship 2, ship 1 and ship 3 are both very small, but the distance between ship 2 and ship 3 is too large. That means the world is broken, so we should print “Goodbye World!”\u003c/p\u003e \n \u003cp\u003eCase #3: It seems that nothing happened.\u003c/p\u003e \n \u003c/div\u003e \n "}}]}