ตน้ ไมค้ือกราฟแบบไม่มีทิศทางที่เชื่อมต่อกนั (connected) และไม่มีวงรอบ (cycle) ให้ต้นไม้ที่มีN โหนด และเส้นเชื่อม N-1 เส้น เราต้องการจะ ระบายสีต้นไม้กล่าวคือเราตอ้งการกา หนดสีให้กบัโหนดต่าง ๆ โดยสีเป็ นจ านวนเต็มจากเซต {1,2,...,K} โดยที่รับประกนัวา่ โหนดที่มีเส้นเชื่อมติดกนั จะมีสีไม่ซ้า กน</p>

ให้คุณเขียนโปรแกรมเพื่อคา นวณว่าสามารถทา ไดก้ี่แบบ เนื่องจากค าตอบสามารถมีได้จ านวนมาก ให้ตอบจ านวนวิธีmodulo 93563

입력 형식

บรรทัดแรก ระบุจ านวนเต็ม T (1 ≤ T ≤ 10) แทนจ านวนข้อมูลชุดทดสอบ จากน้นัจะมีขอ้มูลชุดทดสอบ T ชุด ในรูปแบบดงัน้ี</p>

• บรรทัดแรกของข้อมูลชุดทดสอบระบุจ านวนเต็มสองจ านวน N และ K โดยที่ N แทนจ านวนโหนด (2 ≤ N ≤ 200) และ K แทน จ านวนสีที่สามารถใช้ได้(1 ≤ K ≤ 10) โหนดจะมีหมายเลขต้งัแต่ 1 ถึง N
• อีก N-1 บรรทัด ระบุข้อมูลของเส้นเชื่อมในต้นไม้แต่ละบรรทดัระบุจา นวนเตม็ สองจา นวน A และ B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) ระบุวา่ มีเส้นเชื่อมระหวา่ งโหนดหมายเลข A และ B

มีท้งัสิ้น T บรรทัด สา หรับขอ้มูลนา เขา้แต่ละชุดให้พิมพจ์า นวนวิธีการระบายสีmodulo 93563 เรียงตามล าดับ บรรทดัและหน่ึงค่า

예제 입력

3
2 3
1 2
4 2
1 2
1 3
1 4
5 5
1 2
2 3
3 4
4 5

예제 출력

6
2
1280