{"trustable":false,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\t\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n\t MathJax.Hub.Config({\n\t extensions: [\"tex2jax.js\"],\n\t jax: [\"input/TeX\", \"output/SVG\"],\n\t tex2jax: {\n\t inlineMath: [ [\u0027$\u0027,\u0027$\u0027], [\"\\\\(\",\"\\\\)\"] ],\n\t displayMath: [ [\u0027$$\u0027,\u0027$$\u0027], [\"\\\\[\",\"\\\\]\"] ],\n\t processEscapes: true\n\t },\n\t });\n\t\u003c/script\u003e\n\t\u003cscript type\u003d\"text/javascript\"\n\t src\u003d\"https://cdn.staticfile.org/mathjax/2.7.0/MathJax.js\"\u003e\n\t\u003c/script\u003e\n \n \u003cp\u003e The 11th Zhejiang Provincial Collegiate Programming Contest is coming! As a problem setter, Edward is going to arrange the order of the problems. As we know, the arrangement will have a great effect on the result of the contest. For example, it will take more time to finish the first problem if the easiest problem hides in the middle of the problem list. \u003c/p\u003e \n \u003cp\u003e There are \u003cvar\u003eN\u003c/var\u003e problems in the contest. Certainly, it\u0027s not interesting if the problems are sorted in the order of increasing difficulty. Edward decides to arrange the problems in a different way. After a careful study, he found out that the i-th problem placed in the j-th position will add \u003cvar\u003eP\u003csub\u003eij\u003c/sub\u003e\u003c/var\u003e points of \"interesting value\" to the contest. \u003c/p\u003e \n \u003cp\u003e Edward wrote a program which can generate a random permutation of the problems. If the total interesting value of a permutation is larger than or equal to \u003cvar\u003eM\u003c/var\u003e points, the permutation is acceptable. Edward wants to know the expected times of generation needed to obtain the first acceptable permutation. \u003c/p\u003e \n\u003cbr\u003e现在要安排n道题目的顺序,如果第i到题目放在第j个位置,产生Pij的愉悦度。\n\u003cbr\u003e如果产生总的愉悦度大于等于M,则这个顺序是可以接受的。\n\u003cbr\u003e现在随机产生顺序,期望随机多少次,就可以第一次产生可以接受的排列顺序。\n\n "}},{"title":"Input","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cp\u003eThere are multiple test cases. The first line of input contains an integer \u003cvar\u003eT\u003c/var\u003e indicating the number of test cases. For each test case:\u003c/p\u003e \n \u003cp\u003e The first line contains two integers \u003cvar\u003eN\u003c/var\u003e (1 \u0026lt;\u003d \u003cvar\u003eN\u003c/var\u003e \u0026lt;\u003d 12) and \u003cvar\u003eM\u003c/var\u003e (1 \u0026lt;\u003d \u003cvar\u003eM\u003c/var\u003e \u0026lt;\u003d 500). \u003c/p\u003e \n \u003cp\u003e The next \u003cvar\u003eN\u003c/var\u003e lines, each line contains \u003cvar\u003eN\u003c/var\u003e integers. The j-th integer in the i-th line is \u003cvar\u003eP\u003csub\u003eij\u003c/sub\u003e\u003c/var\u003e (0 \u0026lt;\u003d \u003cvar\u003eP\u003csub\u003eij\u003c/sub\u003e\u003c/var\u003e \u0026lt;\u003d 100). \u003c/p\u003e \n \u003c /h4\u003e\n\u003cbr\u003e第一行一个整数T,表示测试数据组数。\n\u003cbr\u003e对于每组测试数据,第一行两个整数N和M\n\u003cbr\u003e接下来N行,每行N个数,第i行的第j个数表示Pij"}},{"title":"Output","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cp\u003e For each test case, output the expected times in the form of irreducible fraction. An irreducible fraction is a fraction in which the numerator and denominator are positive integers and have no other common divisors than 1. If it is impossible to get an acceptable permutation, output \"No solution\" instead. \u003c/p\u003e \n \u003c/h4\u003e\n\u003cbr\u003e如果永远无法产生,输出\"No solution\"\n\u003cbr\u003e否则输出一个分数p/q,p和q的公约数为1\n \n"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cpre\u003e2\n3 10\n2 4 1\n3 2 2\n4 5 3\n2 6\n1 3\n2 4\n\u003c/pre\u003e \n \u003ch4"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cpre\u003e3/1\nNo solution\n\u003c/pre\u003e \n "}}]}